Blog

题目传送门

看完题面先写了一份暴力

然后竟然AC了

直接模拟

刚开始有30000个小方块

每次移动 都是把一个方块移动到另一个方块上变成一个大方块

可以发现每次移动大方块内的小方块都是先进先出，于是对于每一个方块都可以用队列维护

当我们把 一个小方块x 移动到另一方块y上时，x 下方的方块数目等于移动前 y的所含的方块数目

用d[i]表示方块i下方的方块数目，于是我们可以O（1）查询

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N = 30007;
queue<int> num[N]; // 队列维护 每个大方块里 的小方块 
ll v[N],cnt[N],d[N],n;// v[i] 小方块i在哪个大方块中 ， cnt[i] 大方块i有多少个小方块 ， d[i] 小方块i下方有多少个小方块 
void M(ll x,ll y)
{   
    ll a=v[x],b=v[y];//先记录 x，y 所在的 大方块编号 
    for(ll i=1;i<=cnt[a];++i)
    {   
		//将 x 移入 y 所在的方块  
        ++cnt[b];
        ll now = num[a].front();
        num[b].push(now);
        v[now]=b; 
        num[a].pop();
        // 每次移动都更新 d[i] 
		// now下方的方块数目等于移动前 b的所含的方块数目 
        d[now]=cnt[b]-1; 
    }
}
int main()
{
    n = read();
    for(ll i=1;i<=30000;++i)
    {
		//刚开始对每个小方块 初始化 
        num[i].push(i);
		v[i]=i;
		cnt[i]=1; 
    }
    for(ll i=1;i<=n;++i)
    {
        char c;cin>>c;
        if(c=='M')
        {
            ll x=read(),y=read();
            M(x,y);
        }
        else
        {
            ll x=read();
            printf("%d\n",d[x]);
        }
    }
    return 0;
}