CF1548A

Aryper · 2021-11-15 12:25:43 · 个人记录

Web of Lies

题没读完，惨。

不过正解确实有些巧妙，但也不是那么巧妙（毕竟还是人可以正常想出来的范畴）。

我们不必真的去处理连边和删边的操作。

因为对于每个操作 3，一个点会被删掉，当且仅当存在一个与他相连的点还比他强。

因此不会被删掉的点就是那些与他相邻的点都比他还弱的。

然后统计一下这个数目，动态维护即可。

时间复杂度 O(n+m+q)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,m,q,u,v,ans,op;

ll huger_than[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        if(u>v) huger_than[v]++;
        else huger_than[u]++;
    }

    for(ll i=1;i<=n;i++) {
        if(huger_than[i]==0) ans++;
    }

    q=read();

    while(q--) {
        op=read();
        if(op==1) {
            u=read();v=read();
            if(u>v) {huger_than[v]++;if(huger_than[v]==1) ans--;}
            else {huger_than[u]++;if(huger_than[u]==1) ans--;}
        }
        if(op==2) {
            u=read();v=read();
            if(u>v) {huger_than[v]--;if(huger_than[v]==0) ans++;}
            else {huger_than[u]--;if(huger_than[u]==0) ans++;}
        }
        if(op==3) {
            writeln(ans);
        }
    }

    return 0;
}