题目大意
有 \(N\) 只鸽子，编号从 \(1\) 到 \(N\) ，有 \(N\) 个鸽巢，编号从 \(1\) 到 \(N\) 。最初，鸽子 \(i\) 在 \(1\leq i\leq N\) 的巢 \(i\) 中。
您会收到 \(Q\) 个查询，您必须按顺序处理这些查询。查询有两种类型，每种都以下列格式之一给出：
1 P H: 将鸽子 \(P\) 移至鸽巢 \(H\) 。2: 输出包含一只以上鸽子的鸽巢数量。
思路
我们可以用一个数组记录下每个鸟窝的鸟的只数，再记录下来现在每个鸟在那个窝，再记录下来每个窝中是否有一只以上的鸟（注意：在上面这些记录中，是边输入边进行记录）。接着我们看如果这只鸟转过去的那个窝的只数 \(\ge 2\) 且再转过去之前这个窝没有两只鸟，这时我们就让答案加一。我们再看如果这只鸟转过去之前的那个窝如果现在只数 \(\le 1\) 且这个窝原来是有两只鸟的，这时我们就让答案减一。
AC code：
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define sz(s) s.size()
#define db double
#define mod 1000000007
#define P 998244353
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define per(i,l,r) for(ll i=l;i>=r;i--)
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define in insert
#define y1 y142857
//pair<ll,ll> PII;
//unordered_map<int,int> f;
//vector<int>edges[N];
//set<int>c;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
inline void write(int x,int w,int e){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10,w,e);putchar(x%10+'0');if(x==e){if(w==1)putchar(' ');if(w==2)putchar('\n');}return;
}
//time: O( )
//memory: ()kb
int n,q,a[N],ans=0,ne[N],b[N];
void sovel(){n=read(),q=read();rep(i,1,n)a[i]=1,b[i]=i;rep(_,1,q){int type=read();if(type==1){int p=read(),h=read();a[b[p]]--;a[h]++;if(a[h]>=2&&!ne[h])ne[h]=1,ans++;if(a[b[p]]<=1&&ne[b[p]])ne[b[p]]=0,ans--;b[p]=h;}else{write(ans,2,ans);}}
}
int main(){int T=1;//数据组数while(T--)sovel();
}