题目的意思是把数字像串糖葫芦一样串来串去，询问某个数字下方有多少个数。我看明白了popopopolo的思路后就按他的想法自己写了一个，结果用了282ms，而他的只有32ms，排名第二，差距还真是大orz。仔细对比一下，他的数据类型是short，输入输出函数也是重写的。我试着把int改为short，结果是266ms，基本没什么优化，而我也懒得重写函数了。原来我只知道scanf比cin强，没想到手写的效率要更强。

1 #include 
      
        2 #include 
       
         3 #define N 30005 4 int fa[N],d[N]; 5 int find(int x) 6 { 7     if(fa[x] <= 0) return x; 8     int t = fa[x]; 9     fa[x] = find(t);10     if(t != fa[x])11         d[x] += d[t];12     return fa[x];13 }14 int main()15 {16     int n,a,b,i,x,y;17     char ch;18     scanf("%d",&n);19     getchar();20     memset(fa,-1,sizeof fa);21     while(n--)22     {23         scanf("%c",&ch);24         if(ch == 'M')25         {26             scanf("%d%d",&a,&b);27             x = find(a);28             y = find(b);29             d[x] -= fa[y];30             fa[y] += fa[x];31             fa[x] = y;32         }33         else34         {35             scanf("%d",&a);36             find(a);37             printf("%d\n",d[a]);38         }39         getchar();40     }41     return 0;42 }
       
      

 

……