对于各种并查集写法速度的研究 January 24, 2017 2018.3.3：更新了测试代码，加入了更多写法，修复了一些致命错误 测试机CPU为Intel® Celeron® Processor G3900，内存为8GB DDR4，系统为Debian 9。 编译命令为g++ test.cpp -o test -O3。 先放测试代码： ```c++ #include<cstdio> #include<ctime> #include<random> #include<cassert> #define N 1024 #define T 100000 int fa[N+233],st[N+233],sz[N+233]; int find1(int x) { return x==fa[x]?x:fa[x]=find1(fa[x]); } inline int find2(int x) { return x==fa[x]?x:fa[x]=find2(fa[x]); } inline int find3(int x) { while(x!=fa[x])x=fa[x]=fa[fa[x]];return x; } inline int find4(int x) { int se=0;st[0]=x; while(fa[x]!=x)st[++se]=x=fa[x]; while(se)fa[st[--se]]=x; return x; } inline int find5(int x) { int t=x,p; while(x!=fa[x])x=fa[x]; while(t!=x)p=fa[t],fa[t]=x,t=p; return x; } int find6(int x) { return 0>fa[x]?x:fa[x]=find6(fa[x]); } inline int find7(int x) { return 0>fa[x]?x:fa[x]=find7(fa[x]); } inline int find8(int x) { while(fa[x]>=0&&fa[fa[x]]>=0)x=fa[x]=fa[fa[x]];return fa[x]<0?x:fa[x]; } long long global_checksum; unsigned int count,seed; std::mt19937 ran_(0); void init_rand(int x) { ran_=std::mt19937(x); ran_(),ran_(),ran_(); count=0; } int rand() { if(count&1023)seed=ran_(); count++; seed^=seed<<13; seed^=seed>>17; seed^=seed<<5; return seed; } inline long long test(int(*f)(int)) { init_rand(19260817); long long last,timeusage=0,checksum=0; for(int t=0;t<T;t++) { for(int i=0;i<N;i++)fa[i]=i; last=clock(); for(int i=0,x,y;i<N;i++) { x=rand(),y=rand(); x&=N-1,y&=N-1; x=f(x),y=f(y); if(x!=y)fa[x]=y; } timeusage+=clock()-last; for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0)); } assert(global_checksum==checksum||global_checksum==0); global_checksum=checksum; return timeusage; } inline long long test2(int(*f)(int)) { init_rand(19260817); long long last,timeusage=0,checksum=0; for(int t=0;t<T;t++) { for(int i=0;i<N;i++)fa[i]=i; for(int i=0;i<N;i++)sz[i]=1; last=clock(); for(int i=0,x,y;i<N;i++) { x=rand(),y=rand(); x&=N-1,y&=N-1; x=f(x),y=f(y); if(x!=y){if(sz[x]>sz[y])sz[x]+=sz[y],fa[y]=x;else sz[y]+=sz[x],fa[x]=y;} } timeusage+=clock()-last; for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0)); } assert(global_checksum==checksum||global_checksum==0); global_checksum=checksum; return timeusage; } inline long long test3(int(*f)(int)) { init_rand(19260817); long long last,timeusage=0,checksum=0; for(int t=0;t<T;t++) { for(int i=0;i<N;i++)fa[i]=-1; last=clock(); for(int i=0,x,y;i<N;i++) { x=rand(),y=rand(); x&=N-1,y&=N-1; x=f(x),y=f(y); if(x!=y){if(fa[x]<fa[y])fa[x]+=fa[y],fa[y]=x;else fa[y]+=fa[x],fa[x]=y;} } timeusage+=clock()-last; for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0)); } assert(global_checksum==checksum||global_checksum==0); global_checksum=checksum; return timeusage; } inline long long test2_1(int(*f)(int)) { init_rand(19260817); long long last,timeusage=0,checksum=0; for(int t=0;t<T;t++) { for(int i=0;i<N;i++)fa[i]=i; for(int i=0;i<N;i++)sz[i]=1; last=clock(); for(int i=0,x,y;i<N;i++) { x=rand(),y=rand(); x&=N-1,y&=N-1; x=f(x),y=f(y); if(x!=y){if(sz[x]>sz[y])fa[y]=x;else{fa[x]=y;if(sz[x]==sz[y])sz[y]++;}} } timeusage+=clock()-last; for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0)); } assert(global_checksum==checksum||global_checksum==0); global_checksum=checksum; return timeusage; } inline long long test3_1(int(*f)(int)) { init_rand(19260817); long long last,timeusage=0,checksum=0; for(int t=0;t<T;t++) { for(int i=0;i<N;i++)fa[i]=-1; last=clock(); for(int i=0,x,y;i<N;i++) { x=rand(),y=rand(); x&=N-1,y&=N-1; x=f(x),y=f(y); if(x!=y){if(fa[x]<fa[y])fa[y]=x;else{if(fa[x]==fa[y])fa[y]--;fa[x]=y;}} } timeusage+=clock()-last; for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0)); } assert(global_checksum==checksum||global_checksum==0); global_checksum=checksum; return timeusage; } int main() { printf("CLOCKS_PER_SEC:%d\n",CLOCKS_PER_SEC); printf("find1:%lld %lld %lld\n",test(find1),test2(find1),test2_1(find1)); printf("find2:%lld %lld %lld\n",test(find2),test2(find2),test2_1(find2)); printf("find3:%lld %lld %lld\n",test(find3),test2(find3),test2_1(find3)); printf("find4:%lld %lld %lld\n",test(find4),test2(find4),test2_1(find4)); printf("find5:%lld %lld %lld\n",test(find5),test2(find5),test2_1(find5)); printf("find6:%lld %lld\n",test3(find6),test3_1(find6)); printf("find7:%lld %lld\n",test3(find7),test3_1(find7)); printf("find8:%lld %lld\n",test3(find8),test3_1(find8)); } ``` 当N=1024,T=500000时，输出： ``` find1:20089351 15887467 16531550 find2:20097390 15910071 16540963 find3:17256541 13390076 13982165 find4:19644034 15645215 16138683 find5:19427605 15368866 15878426 find6:15846219 16573551 find7:15818575 16527184 find8:14988614 15839679 ``` 当N=131072,T=5000时，输出： ``` CLOCKS_PER_SEC:1000000 find1:40043295 28478678 29630797 find2:40079319 28487803 29605407 find3:34651392 23403124 24607184 find4:40438077 27544080 28666981 find5:39498635 26400323 27404284 find6:25862629 26859295 find7:25814962 26853594 find8:24541376 25698358 ``` 当N=2097152,T=500时，输出： ``` CLOCKS_PER_SEC:1000000 find1:240728970 173155213 166865669 find2:240076225 173137194 166896002 find3:257240885 186958166 159086582 find4:240671337 168750996 164743633 find5:210863641 130934764 128655852 find6:107561256 107685991 find7:107630995 107676199 find8:101390000 100197421 ``` 当N=16777216,T=400时，输出： ``` CLOCKS_PER_SEC:1000000 find1:2537867344 1538207603 1438028041 find2:2542492294 1537816024 1438141065 find3:2878818361 1750536054 1388536804 find4:2497444413 1495104276 1413699601 find5:2212506256 1083761103 1015381467 find6:983906431 926941775 find7:984064763 926552621 find8:892107319 808279658 ``` （原结果有误，已删） 最后得出的结果是find8（while非递归+按秩合并+秩和fa记在一个数组上）最快，当N较小时秩选用size，当N较大时秩选用depth。 当不方便非递归时可以写递归的（find6或find7）。 inline似乎没有明显优化。
BZOJ 3160: 万径人踪灭 January 20, 2017 ###Description 略。见[BZOJ3160][1] ###Solution 对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者manacher可以得出 考虑以每个位置为中心的对称元素对个数f[i]，那么i位置对答案的贡献是$$2^{f[i]}-1$$ 如果把a视为1，b视为-1，然后把原串长度\*4，卷积，那么以i为中心的元素对如果相同，则贡献1，否则贡献-1 ###Code ```c++ #include<bits/stdc++.h> typedef double lf; #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) inline int mod(int x,int y){if(x>=y)return x-y;return x;} #define N 524288 struct num { lf r,i; num(){r=i=0;} num(lf x){r=x,i=0;} num(lf x,lf y){r=x,i=y;} num(const num &x){r=x.r,i=x.i;} inline num& operator +=(const num &x){r+=x.r,i+=x.i;} inline num& operator -=(const num &x){r-=x.r,i-=x.i;} inline num& operator *=(const num &x){lf a=r*x.r-i*x.i,b=r*x.i+i*x.r;r=a,i=b;} inline num operator +(const num &x){num t=*this;t+=x;return t;} inline num operator -(const num &x){num t=*this;t-=x;return t;} inline num operator *(const num &x){num t=*this;t*=x;return t;} }; int id[N]; num tx[N],mf[N]; inline void init_id(int y) { fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1; } #define idft(a,b) dft(a,b,1) inline void dft(num *s,int n,bool II=0) { fo0(i,1<<n)tx[i]=s[id[i]]; fo1(p,n) { lf tmp=M_PI*2/(1<<p); if(II)tmp=-tmp; num t0(1),t1(cos(tmp),sin(tmp)); fo0(i,1<<p-1)mf[i]=t0,t0*=t1; num X,Y; for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir) { X=tx[i|j],Y=tx[i|j|ir]*mf[j]; tx[i|j]=X+Y,tx[i|j|ir]=X-Y; } } fo0(i,1<<n)s[i]=tx[i]; } #define N2 100010 struct node { int len,cnt; node *nxt[2],*fail; }t[N2+2],*tm=t+2; inline void build(char *s,int n) { t[0].len=0,t[1].len=-1; node *cur=t+1,*tmp,*t2; t[0].fail=t+1; for(int i=0;i<n;i++) { char u=s[i]-'a'; for(;s[i]!=s[i-1-cur->len];cur=cur->fail); if(cur->nxt[u]) cur=cur->nxt[u],cur->cnt++; else { tmp=cur->nxt[u]=tm++; tmp->len=cur->len+2; tmp->cnt=1; if(tmp->len==1) tmp->fail=t; else { for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail); tmp->fail=t2->nxt[u]; } cur=tmp; } } } inline void count() { for(node *x=tm-1;x>=t;x--) if(x->fail)x->fail->cnt+=x->cnt; } #define P 1000000007 inline int cnt() { int ans=0; for(node *x=tm-1;x>t+1;x--) ans=mod(ans+x->cnt,P); return ans; } char s[100000]; num p[N]; int po[100001]; int main() { scanf("%s",s); int n=strlen(s); fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P); int y=0; while((1<<(y+1))<n*4)y++;y++; fo0(i,n)p[i]=s[i]=='a'?1:-1; init_id(y); dft(p,y); fo0(i,1<<y)p[i]*=p[i]; idft(p,y); lf t=1.0/(1<<y); int ans=0; fo0(i,n*2-1) { int cnt=round(p[i].r*t); cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2; ans=mod(ans+po[cnt],P); } build(s,n); count(); printf("%d",mod(ans+P-cnt(),P)); } ``` [1]: http://www.lydsy.com/JudgeOnline/problem.php?id=3160
BZOJ 2989: 数列 & 4170: 极光 January 8, 2017 ###Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。 2种操作（k都是正整数）： 1.Modify x k：将第x个数的值修改为k。 2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计） ###Input 第1行两个整数n,q。分别表示数列长度和操作数。 第2行n个正整数，代表初始数列。 第3--q+2行每行一个操作。 ###Output 对于每次询问操作，输出一个非负整数表示答案 ###Sample Input 3 5 2 4 3 Query 2 2 Modify 1 3 Query 2 2 Modify 1 2 Query 1 1 ###Sample Output 2 3 3 ###HINT N<=60000 修改操作数<=40000 询问<=60000 Max{a[i]}含修改<=100000 ###Solution 这道题其实是维护两种操作，向平面上加点，查询菱形内点数 把(x,y)变为(x+y,x-y)，菱形就变成了正方形 假设某个询问是以(x0,y0)为中心，边长为2k的正方形，那么可以拆成两个，一个是x>=x0-k且x<=x0+k且y<=y0+k的点数，另一个是x>=x0-k且x<=x0+k且y<y0-k的点数，把两个询问做差就和原询问相同 那么可以CDQ分治，按y排序，x用树状数组维护 ###Code ```c++ #include<bits/stdc++.h> using namespace std; int n,m,s[60001],ans[60000],ac,qc,mx; struct query { int x,y,k,id;char op; }q[230000],tmp[230000]; inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);} int p[160001]; inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;} inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;} inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;} void work(int l,int r) { if(l==r)return; int mid=(l+r)>>1; work(l,mid),work(mid+1,r); int i1=l,i2=mid+1,ti=l; for(;i2<=r;tmp[ti++]=q[i2++]) { for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++]) if(!q[i1].op)pl(q[i1].x); if(q[i2].op) { if(q[i2].op==1) ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1); else ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k); } } for(;i1<=mid;tmp[ti++]=q[i1++]); for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x); for(i1=l;i1<=r;i1++)q[i1]=tmp[i1]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",s+i),add(i,s[i]); char tmp[10];int a,b; while(m--) { scanf("%s%d%d",tmp,&a,&b); if(tmp[0]=='M') add(a,s[a]=b); else { int x=a+s[a],y=a-s[a]; q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++; q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++; ac++; } } work(0,qc-1); for(int i=0;i<ac;i++) printf("%d\n",ans[i]); } ```
BZOJ 4750: 密码安全 January 1, 2017 ###Description 有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复杂程度。 ![aa.jpg][1] 的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对10^9+61 取模的值即可。 ###Input 第一行包含一个正整数 T ，表示有 T 组测试数据。 接下来依次给出每组测试数据。对于每组测试数据： 第一行包含一个正整数 n 。 第二行包含 n 个非负整数，表示 A_1,A_2,?,A_n 。 保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。 100% 的数据满足：1≤T≤200,1≤n≤10^5,1≤∑n≤10^6,0≤A_i≤10^9 ###Output 对于每组数据输出一行，包含一个整数，表示答案对10^9+61 取模的值。 ###Sample Input 3 1 61 5 1 2 3 4 5 5 10187 17517 24636 19706 18756 ###Sample Output 3721 148 821283048 ###Solution 单调栈扫一遍得到以每个数为最大值的区间，然后按位记前缀xor和的前缀和，对每个数分别统计答案 ###Code ```c++ #include<bits/stdc++.h> #define P 1000000061 int s[100001],S[100001],l[100001],r[100001],G[100010],*C=G+9; int main() { int T;for(scanf("%d",&T);T--;) { int n,m=0,i,j,t,p,A=0; scanf("%d",&n);s[n]=2e9; for(i=0;i<n;i++)scanf("%d",s+i); for(i=0;i<=n;i++) { while(m&&s[i]>=s[S[m-1]])r[S[--m]]=i-1; l[i]=m?S[m-1]+1:0,S[m++]=i; } for(j=0;j<30;j++) { for(i=t=p=0;i<n;i++)C[i]=t+=p^=s[i]>>j&1; for(i=0;i<n;i++) { t=C[i-1]-C[l[i]-2],p=C[r[i]]-C[i-1]; A=(((1ll*t*(r[i]-i+1-p)+1ll*p*(i-l[i]+1-t))%P<<j)%P*s[i]+A)%P; } } printf("%d\n",A); } } ``` [1]: /usr/uploads/2017/01/1896004125.jpg