OI题解 - Zamjene [COCI 2016/2017 Round 2] | Lucky_Glass's Blog
0%

OI题解 - Zamjene [COCI 2016/2017 Round 2]

听说以后的练习赛都是 COCI 的题呢(虽然不熟悉这个系列的比赛,但是总觉得特别高级QwQ)

然后这是一道不错的题~


· 题目

温馨提示:题目繁杂,下有翻译

Dominik 想象出了一系列正整数 $P_1 ,P_2 ,…,P_n$ 。让我们将他们排序之后的版本称为 $Q_1 ,Q_2 ,…,Q_n$ 。
此外 , 他想象出了一个允许替换集合 。 如果一对 $(X ,Y)$ 是允许替换集合的成员,Dominik 可以交换数组 $P$ 中位于 $X$ 和 $Y$ 处的数字。
Marin 向 Dominik 进行了 $T$ 次查询,每个查询都属于以下类型之一:

  1. 把数组 $P$ 中位于 $A$ 和 $B$ 位置的两个数字交换。
  2. 将 $(A,B)$ 添加到允许替换集合中 。Marin 可能给出已经在允许替换集合中的数对$(A,B)$。
  3. 看看是否可以仅使用允许替换集合中的替换进行排序?可以以任意顺序使用替换,并且可以使用每个替换任意次数。
  4. 如果位于 $A$ 位置的数字可以仅使用允许的替换转移到位置 $B$, 那么我们称 $A$ 和 $B$ 是链接的 。 我们把所有和 $A$ 链接的位置构成的集合称为 $A$ 的云 。如果对于一个云中的每个元素 $j$ ,都能在仅使用允许替换集合中的替换使得 $P_j=Q_j$ ,那么我们称这个云是好的 。 你必须回答有多少对不同的满足以下条件的位置 $(A,B)$ :
    ① 位置 $A$ 和 $B$ 不是链接的;
    ② $A$ 和 $B$ 的云都不是好的;
    ③ 如果我们将对 $(A,B)$ 添加到允许的替换集合中,$A$ 的云(通过使 $A$ 和 $B$ 成为链接的来得到)变为好的。请注意:对 $(A,B)$ 和 $(B,A)$ 被认为是完全相同的一对位置。

· 解析

- 题意

我觉得为了reader们读题不这么懵逼,还是翻译一下题目……

有一个包含 $n$ 个数的数组 $P$ ,将它从小到大排序后我们会得到数组 $Q$ 。

我们现在对 $P$ 的一些位置(不是数字)进行操作:

  1. 给定 正整数$A,B$ ,交换 $P$数组 的 $A$位置 和 $B$位置 上的数;
  2. 给定 正整数$A,B$,我们把 $A$位置 和 $B$位置 连接起来。
  3. 如果 $A,B$ 位置是连接的,那么我们可以交换 $P$数组 $A$位置 和 $B$位置 上的数;问能否通过若干次交换,使 $P$数组 与 $Q$数组 相同(只需要各个位置的数值相等)。如果能,输出 “DA”,否则输出 “NE”。
  4. 定义“云”为一个集合,当且仅当 $A$位置 和 $B$位置 直接或间接相连,$A$ 和 $B$ 属于一个云。换个说法,如果我们把 “连接$A位置,B位置$” 看成 “在 $A位置,B位置$ 之间连一条边”,那么一个云就是一个连通块

    定义一个云$A$是“好”的,当且仅当$\{P_i|i\in A\}=\{Q_i|i\in A\}$。

    求解有多少个数对 $(X,Y)$ 满足以下条件:(在这里 $(X,Y)$ 和 $(Y,X)$ 没有区别)

    • $X,Y$ 不在同一个云内;
    • $X,Y$ 所在的云都不是好的;
    • 若连接 $X,Y$,则 $X,Y$ 原本所在的云合为一个云,满足合并得到的云是好的。

- 处理云

按照定义,可以发现在没有进行任何操作的时候,每个位置各自属于一个云。

当我们连接 $A,B$位置 时,$A$ 所在的云 就和 $B$所在的云 合并了……支持合并操作的数据结构?——并查集

最初每个位置都是一个并查集,也就是 $cld_i=i$ ($cld$数组是并查集数组,如果$cld_i=cld_j$,那么$i,j$在同一个并查集里);当我们连接 $A,B$ 时,只需要把 $A,B$ 所在并查集合并就行了。

对于并查集$A$,我们定义:

  • $siz_A$ 表示并查集的大小;
  • $cldP_A$ 是一个数组:数组的第 $x$ 个元素的值是 “并查集中满足 $P_t=x$ (还记得数组$P$吗?就是题目中提到的那个)的元素$t$的个数”;
  • $cldQ_A$ 是一个数组:数组的第 $x$ 个元素的值是 “并查集中满足 $Q_t=x$ (还记得数组$Q$吗?就是题目中提到的那个)的元素$t$的个数”;

下面我们考虑怎么合并并查集$X$和并查集$Y$。(也就是合并云$X$和云$Y$)

首先 $cld_Y=X$,这是我自己的做法——把$Y$的数据合入$X$里。

然后 $cldP_X$ 和 $cldP_Y$ 的对应位置相加,并且 $cldQ_X$ 和 $cldQ_Y$ 的对应位置相加,也就是 $Y$ 的所有元素与 $X$ 的元素合并。

最后 $siz_X+=siz_Y$,也就是更新合并后的并查集大小。

- 哈希合并加速

我们会发现在合并并查集$X,Y$时,由于我们要将 $cldP$ 和 $cldQ$ 的对应位置相加,这个操作就会变成 $O(n)$ 的,在多次询问的情况下肯定是会 TLE 的,所以我们考虑哈希——

定义一个质数常数 $prn$ ,我这里取用的是 $prn=1000016107$ (是随便取的一个大于 $10^9$ 的数)。
然后把 $cldP$ 数组的第 $i$ 个元素作为一个 $prm$ 进制数的第 $i$ 位,以这个 $prm$进制数 作为 $cldP$ 的哈希值。哈希值用 unsigned long long 储存,自然溢出。
对于 $cldQ$ 也这样处理。

这样我们就把 $cldP,cldQ$ 由数组转换为数字。而且因为它只是一个 $prm$进制数,合并 并查集$X,Y$ 时只需要让 $cldP_X+=cldP_Y,cldQ_X+=cldQ_Y$ 就可以了。

这样操作1,2不就 $O(1)$ 了吗?

- 查询加速

= 加速操作 3

由于时间限制,我们不可能每次操作3时,都模拟排序一遍。

但是我们知道,当且仅当每一个云都是好的,经过若干次交换后,$P$可以变得和 $Q$ 相同。
所以我们定义 $numgood$ 是好的云的个数,$numcld$ 是云的总个数(因为合并云的时候云的个数会减一,所以储存 $numcld$ 是有必要的)。当 $numgood=numcld$ 时,经过若干次交换,$P$ 可以变为 $Q$。

只有交换元素或合并云(操作1,2)的时候 $numgood$ 会改变——所以在交换 $X,Y$ 中的元素或合并 $X,Y$ 时,我们先在 $numgood$ 中减去 $X,Y$ 中好的云的个数,交换或合并完后,我们把得到的云中好的云的个数加回 $numgood$ 里。

这样就实现操作 3 $O(1)$ 了!

= 加速操作 4

这是最复杂的一个操作。

可以发现如果数对 $(i,j)$ 满足操作4的要求(忘了要求的上去看题目),那么 $i$ 所在云$X$ 中的每个元素与 $j$ 所在云$Y$中的每个元素都可以构成一个符合要求的数对。

那么我们就不单个考虑元素,而是考虑一对云。根据定义,我们可以知道:当且仅当 $X,Y$都不是好的云 且 $cldP_X+cldP_Y=cldQ_X+cldQ_Y$ 时,$X$的每个元素 与 $Y$的每个元素 都能构成一个符合要求的数对(下文简称“$X$的每个元素 与 $Y$的每个元素 都能构成一个符合要求的数对”为“$X,Y$配对”)。
我们把 $cldP_X+cldP_Y=cldQ_X+cldQ_Y$ 变一下形—— $cldP_X-cldQ_X=cldQ_Y-cldP_Y$ 。也就是说当 $X,Y$ 满足 $cldP_X-cldQ_X=cldQ_Y-cldP_Y$ 且 $X,Y$都不是好的云 时,$X,Y$ 配对,则可以构造出 $siz_X\times siz_Y$ 个数对。

定义 $cnt_i$ 表示所有 $cldP_X-cldQ_X=i$ 的云$X$的元素个数之和。对于 云$X$ ,它包含的每个元素可以和 $cnt_{cldQ_X-cldP_X}$ 个元素构成一个数对,那么云$X$对操作4的答案的“贡献”为 $siz_X\times cnt_{cldQ_X-cldP_X}$ 。

img1

记操作4的答案为 $numpair$ (注意这道题的 numpair 要开 long long)。

显然仍然只会在操作1,2时 $numpair$ 会改变。

  1. 操作1

    假设要交换数字的两个位置分别属于云$X,Y(X\not=Y)$ 。

    那么在交换之前,我们在分别减去 $X,Y$ 对 $numpair$ 的贡献:
    (如果$X$不是好云)$numpair-=siz_X\times cnt_{cldQ_X-cldP_X}$
    (如果$Y$不是好云)$numpair-=siz_Y\times cnt_{cldQ_Y-cldP_Y}$
    但是就出现了一个问题:如果 $X,Y$ 是配对的呢?
    因为题目所求的数对是无序的,所以当 $X,Y$ 配对时,我们就多减了一个 $X,Y$ 之间的贡献,就像容斥原理一样,我们需要把多减去的贡献加回去:$numpair+=siz_X\times siz_Y$

    img2

    在交换之后先更新 $cnt,cldP$ 。

    再用同样的操作将修改后$X,Y$ 分别的贡献加到 $numpair$ 上去。

  2. 操作2

    先分别减去 $X,Y$ 对 $numpair$ 的贡献,与操作1相同。

    合并后先更新 $cnt,cldP$ ,再加入合并后得到的$X$云对 $numpair$ 的贡献,即 $numpair+=siz_X\times cnt_{cldQ_X-cldP_X}$ 。

查询时输出 $numpair$ 就好啦~

这不就 $O(1)$ 了吗?

(其实我的代码是 $O(log n)$,因为我用的 map 储存 $cnt$ ,不然就还要写一个哈希来处理 $cnt$ 数组的大下标)


· 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef unsigned long long ull;
const int N=1e6;

const ull prn=1000016107;
ull pow_prn[N+5],cldP[N+5],cldQ[N+5];

int P[N+5],cld[N+5],siz[N+5];
int n,m,num_good,num_cld;
long long num_pair;

int CloudFind(int u) {
return cld[u]=(cld[u]==u? u:CloudFind(cld[u]));
}

int Read() {
char c=getchar();
int a=0,b=1;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') a=(a<<3)+(a<<1)+c-'0',c=getchar();
return a*b;
}

map<ull,int> cnt;

int main() {
freopen("zamjene.in","r",stdin);
freopen("zamjene.out","w",stdout);
/*---处理hash质数幂---*/
pow_prn[0]=1;
for(int i=1; i<=N; i++) pow_prn[i]=pow_prn[i-1]*prn;
n=Read();
m=Read();
/*---初始化云的个数---*/
num_cld=n;
/*---输入P并计算Q(siz)---*/
for(int i=1; i<=n; i++)
P[i]=Read(),
siz[i]=P[i]; //siz暂存Q
sort(siz+1,siz+1+n);
/*---初始化云并计算最初好的云的个数---*/
for(int i=1; i<=n; i++) {
cld[i]=i;
cldP[i]=pow_prn[P[i]];
cldQ[i]=pow_prn[siz[i]];
if(cldP[i]==cldQ[i]) num_good++;
}
/*---计算cnt以及pair的个数---*/
for(int i=1; i<=n; i++) {
siz[i]=1;
if(cldP[i]!=cldQ[i]) num_pair+=siz[i]*cnt[cldQ[i]-cldP[i]];
cnt[cldP[i]-cldQ[i]]++;
}
/*---处理询问---*/
while(m--) {
int knd;
knd=Read();
switch(knd) {
/*---询问1---*/
case 1: {
int A,B;
A=Read(),B=Read();
/*---查询云---*/
int cldA=CloudFind(A),cldB=CloudFind(B);
/*---排除同一云---*/
if(cldA==cldB) {
swap(P[A],P[B]);
break;
}
/*---计算AB云中有多少个是好的---*/
int delta=(cldP[cldA]==cldQ[cldA])+(cldP[cldB]==cldQ[cldB]);
/*---减去原来的AB云对的贡献pair---*/
if(cldP[cldA]!=cldQ[cldA])
num_pair-=siz[cldA]*cnt[cldQ[cldA]-cldP[cldA]];
if(cldP[cldB]!=cldQ[cldB])
num_pair-=siz[cldB]*cnt[cldQ[cldB]-cldP[cldB]];
if(cldP[cldA]!=cldQ[cldA] && cldP[cldA]-cldQ[cldA]==cldQ[cldB]-cldP[cldB])
num_pair+=siz[cldA]*siz[cldB];
cnt[cldP[cldA]-cldQ[cldA]]-=siz[cldA];
cnt[cldP[cldB]-cldQ[cldB]]-=siz[cldB];
/*---更改AB云中的P,Q---*/
cldP[cldA]-=pow_prn[P[A]];
cldP[cldA]+=pow_prn[P[B]];
cldP[cldB]-=pow_prn[P[B]];
cldP[cldB]+=pow_prn[P[A]];
swap(P[A],P[B]);
/*---计算新的AB云中的好的个数与原来的差值---*/
delta=(cldP[cldA]==cldQ[cldA])+(cldP[cldB]==cldQ[cldB])-delta;
/*---更新好的云的总个数---*/
num_good+=delta;
/*---加上新的AB云对pair的贡献---*/
cnt[cldP[cldA]-cldQ[cldA]]+=siz[cldA];
cnt[cldP[cldB]-cldQ[cldB]]+=siz[cldB];
if(cldP[cldA]!=cldQ[cldA])
num_pair+=siz[cldA]*cnt[cldQ[cldA]-cldP[cldA]];
if(cldP[cldB]!=cldQ[cldB])
num_pair+=siz[cldB]*cnt[cldQ[cldB]-cldP[cldB]];
if(cldP[cldA]!=cldQ[cldA] && cldP[cldA]-cldQ[cldA]==cldQ[cldB]-cldP[cldB])
num_pair-=siz[cldA]*siz[cldB];
break;
}
case 2: {
int A,B;
A=Read(),B=Read();
/*---查询云---*/
int cldA=CloudFind(A),cldB=CloudFind(B);
/*---排除同一云---*/
if(cldA==cldB) break;
/*---删除B云的个数---*/
num_cld--;
/*---删除AB云的贡献---*/
if(cldP[cldA]!=cldQ[cldA])
num_pair-=siz[cldA]*cnt[cldQ[cldA]-cldP[cldA]];
if(cldP[cldB]!=cldQ[cldB])
num_pair-=siz[cldB]*cnt[cldQ[cldB]-cldP[cldB]];
if(cldP[cldA]!=cldQ[cldA] && cldP[cldA]-cldQ[cldA]==cldQ[cldB]-cldP[cldB])
num_pair+=siz[cldA]*siz[cldB];
cnt[cldP[cldA]-cldQ[cldA]]-=siz[cldA];
cnt[cldP[cldB]-cldQ[cldB]]-=siz[cldB];
/*---计算AB云中有多少个是好的---*/
int delta=(cldP[cldA]==cldQ[cldA])+(cldP[cldB]==cldQ[cldB]);
/*---合并AB云---*/
cld[cldB]=cldA;
siz[cldA]+=siz[cldB];
siz[cldB]=0;
/*---更改AB云中的P,Q---*/
cldP[cldA]+=cldP[cldB];
cldQ[cldA]+=cldQ[cldB];
cldP[cldB]=cldQ[cldB]=0;
/*---计算新的AB云中的好的个数与原来的差值---*/
delta=(cldP[cldA]==cldQ[cldA])-delta;
/*---更新好的云的总个数---*/
num_good+=delta;
/*---加入新的A云的贡献---*/
if(cldP[cldA]!=cldQ[cldA]) num_pair+=siz[cldA]*cnt[cldQ[cldA]-cldP[cldA]];
cnt[cldP[cldA]-cldQ[cldA]]+=siz[cldA];
break;
}
case 3: {
printf("%s\n",num_good==num_cld? "DA":"NE");
break;
}
case 4: {
printf("%lld\n",num_pair);
break;
}
}
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~