POJ 1988 Cube Stocing【権利を持って集計統計を調べる】

Cube Stocing
Time Limit: 2000 MS
 
メモリLimit: 30000 K
Total Submissions: 28711
 
Acceepted: 10081
Case Time Limit: 1000 MS
Description
Farmer John and Betsy are playing a game with N(1<=N==30,000)identical cubes labeled 1 through N.They start with N stacks,each containing a single cube.Farmer John asks Bets Bets Betsy to perform(1=Theropere of)  moves and counts.  * In a move operation,Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.  * In a count operation、Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.  Write a program that can verify the result of the game. 
Input
*Line 1:A single integer、P  * Lines.P+1:Each of these line s describes a legal operation.Line 2 describes the first operation,etc.Each line begins with a'M'for a move operation or a'C'for a count operation.For operation.For operation.the line also contains a single integer:X.Note that the value for N does not appar in the input file.No move operation will request a move a stack onto itelf. 
Output
Print the output from each of the count operation s in the same order as the input file. 
Sample Input

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

Sample Output

1
0
2

ソurce
USACO 2004 U S Open
問題リンク:POJ 1988 Cube Stocing
問題の説明:n個の同じ立方体があります.(1から番号を付けます.)nヒープがあります.P回の操作があります.毎回2種類の選択があります.M X Yを操作します.立方体Xを含む一山を移動します.立方体Yを含む一山の上で、二C Xを操作して、立方体Xの下の立方体の個数を調べます.クエリー操作ごとに、該当する答えを出力します.
問題解決の考え方:権力を持って、各立方体は一番上の立方体を祖先の結点とし、結点iの祖先結点をjとし、cnt[i]は結点iからjまでの立方体数を表し、sum[j]は結点jを先祖の結点とする立方体数を表し、C iの結果はsum[j]-cnt[i]である.
ACのC++コード:

#include

using namespace std;

const int N=30010;
int pre[N],cnt[N],sum[N];//pre    i    ，cnt    i           ，sum     i          

void init()
{
	for(int i=0;i