并查集。
题意是，原有30,000个栈，每个栈中有一个cube，总共最多100,000个操作，每个操作可以是将一个栈叠到另一个上，或者是求某个cube下方有多少个cube。
很明显的”由cube指定的stack号来作叠置操作”暗示了要用并查集的。但以前写过的并查集仅能够实现（1）路径压缩；（2）按秩合并。也即f[i]表示的值可以是（1）栈编号(当f[i]>=0；（2）栈大小(当f[i]<0)。由此，不难推出，如果额外增设一个p[i]，记录每个cube到栈顶间有多少个cube，那么就可以有： 栈大小 – 上方cube数 – 1 = 下方cube数。 进一步分析p[i]的更新方式，每次作union(a,b)时，是将a整个放在b上的，也即此时p[b]=f[a]。但如果要使p[i]值正确，压缩路径前要记录原父cube，递归处理压缩路径后，将父cube的p值累加到本cube的p值上。 跑出来只有500+ms，改成非递归可能才会快点。
|
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 |
#include<cstdio> #include<cstring> char s[2]; int m,f[30000],p[30000]; int fi(int i) { if(f[i]<0) return i; int j=f[i]; f[i]=fi(f[i]); p[i]+=p[j]; return f[i]; } void un(int a,int b) { int fa=fi(a),fb=fi(b); p[fb]=f[fa]; f[fa]+=f[fb]; f[fb]=fa; } void init() { memset(f,-1,sizeof f); memset(p,0,sizeof p); } void solve() { int i,j,k,l; while(m--) { scanf("%s",s); if(s[0]=='M') { scanf("%d%d",&i,&j); un(i-1,j-1); } else { scanf("%d",&i); i--; j=fi(i); printf("%d\n",p[i]-f[j]-1); } } } int main() { while(~scanf("%d",&m)) { init(); solve(); } return 0; } |