题解：AT_abc391_c [ABC391C] Pigeonhole Query

· · 题解

思路：

当为操作 1 时，

如果那只鸽子原来所在的巢有 2 只鸽子，则将答案减 1。 然后把鸽子原来的巢的鸽子数减 1 并将鸽子改到新的巢。

如果新的巢有 1 只鸽子，那么把答案加 1，并把新的巢的鸽子数加 1。

当为操作 2 时，

输出答案即可。

代码：

#include<bits/stdc++.h>
//#define int long long
#define gcd(x,y) __gcd(x,y) 
using namespace std;
int n,q,ans,a[1000005],b[1000005];
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i) a[i]=1,b[i]=i;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            if(a[b[x]]==2) --ans;
            --a[b[x]];
            b[x]=y;
            if(a[y]==1) ++ans;
            ++a[y];
        }
        else{
            cout<<ans<<'\n';
            /*
            for(int i=1;i<=n;++i)
                cerr<<a[i]<<' ';
            cerr<<'\n';*/
        }
    }
    return 0;
}