poj 1988 Cube Stacking

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

 1 #include <stdio.h>
 2 #include <string.h>
 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         else
34         {
35             scanf("%d",&a);
36             find(a);
37             printf("%d\n",d[a]);
38         }
39         getchar();
40     }
41     return 0;
42 }

……