题目描述
约翰和贝茜在玩一个方块游戏。编号为1…n的n(1≤n≤30000)个方块正放在地上,每个构成一个立方柱。
游戏开始后,约翰会给贝茜发出P(1≤P≤100000)个指令。指令有两种:
移动(M):将包含 X 的立方柱移动到包含 Y 的立方柱上。
统计(C):统计含 X 的立方柱中,在 X 下方的方块数目。
写个程序帮贝茜完成游戏。输入
第1行输入P,之后P行每行输入一条指令,形式为 M X Y 或者 C X。
输入保证不会有将立方柱放在自己头上的指令。输出
输出共P行,对于每个统计指令,输出其结果。
样例
输入
6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4输出
1 0 2
- //带权并查集
- #include
- using namespace std;
- int f[40010] , dis[40010] , len[40010];
- int p;
- int find( int x ){
- if ( x == f[x] ) return x;
- else{
- int t = f[x];
- f[x] = find(f[x]);
- dis[x] = dis[x] + dis[t];
- return f[x];
- }
- }
- void merge(int x, int y){
- int fx = find(x) , fy = find(y);
- if ( fx != fy ){
- f[fx] = fy;
- dis[fx] = dis[fx] + len[fy];
- len[fy] = len[fy] + len[fx];
- len[fx] = 0;
- }
- }
- int main(){
- cin >> p;
- for ( int i = 1 ; i <= 30000 ; i++ ){
- f[i]=i;
- len[i] = 1;
- }
- char c;
- int x , y , ans[100010] , k=1;
- for ( int i = 1 ; i <= p ; i++ ){
- cin >> c >> x;
- if ( c == 'C' ){
- find(x);
- ans[k++] = dis[x] ;
- }
- else{
- cin >> y;
- merge(x , y);
- }
- }
- for ( int i = 1 ; i <= k-1 ; i++ )
- printf("%d\n" , ans[i]);
- return 0;
- }