AT_abc391_c 题解

ikunTLE · 2025-02-01 21:43:42 · 题解

题目传送门

思路

首先用 A_i 代表第 i 个鸟巢里有多少只鸽子，T_i 代表第 i 只鸽子在哪个鸟巢里。故初始化 A_i=1，T_i=i。

然后模拟。初始化答案计数器 C=0。

• 若进行操作 1：
  • 先模拟鸽子飞出去，即 A_{T_P}\gets A_{T_P}-1。若此时 A_{T_P}=1，说明这个鸟巢由多只鸽子变为单只鸽子，C\gets C-1。
  • 再模拟鸽子飞进来，即 A_H\gets A_H+1。若此时 A_H=2，说明这个鸟巢由单只鸽子变为多只鸽子，C\gets C+1。同时更改 T_P=H，代表第 P 只鸽子飞进了第 H 个鸟巢。
• 若进行操作 2：输出答案计数器 C 即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,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;}
const int N=1e6+10;
int a[N],p[N];
signed main(){
    int n=read(),q=read();
    for(int i=1;i<=n;++i)
        a[i]=1,p[i]=i;
    int cnt=0;
    while(q--){
        int op=read();
        if(op==1){
            int x=read(),y=read();
            --a[p[x]];
            if(a[p[x]]==1)
                --cnt;
            p[x]=y,++a[y];
            if(a[y]==2)
                ++cnt;
        }
        else printf("%d\n",cnt);
    }
    return 0;
}