C. Web of Lies

题目有点长 题目大意 给3个操纵 1 u v 在u，v之间加一个关系 2 u v 把u v关系删除 3 查询剩余的人数

某人死亡的条件必须满足两个条件 1. 至少一个朋友 2. 所有的朋友都比他权值大(权值为1–n的编号)

1 <=n <= 2e5 0 <= m <= 2e5 n个人 m个原始关系 1 <= q <= 2e5 个查询

可以发现在查询中 要保证时间复杂度为O(q) 或者 O(qlogq)

最开始想到建图 但是发现就算建出来之后再加上每次查询图 时间复杂度也不够

便开始想能否O(1) 查询答案 可以发现 只要u,v中 编号小的必然死亡 可以用ans记录死亡人数 d[]数组 记录死了多少次

那么q查询直接输出 n - ans 就行 O(q) 时间复杂度

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef pair <int, int> PII;
int d[maxn]; //死了多少次 
int main()//至少有一个朋友 所有朋友的权力都比他高 
{
    int n, m;
    scanf("%d %d", &n, &m);
    int ans = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        if(d[min(u, v)] == 0)
        {
            ans ++;
        }
        d[min(u, v)] ++; 
    }
    int q; //编号最小的死 
    scanf("%d", &q);
    while(q --) // O(n) o(nlogn) O(1) 
    {
        int a;
        scanf("%d", &a);
        if(a != 3)
        {
            int u, v;
            scanf("%d %d", &u, &v);
            if(a == 1) //增加一个关系 
            {
                if(!d[min(u, v)])//没死过 
                ans ++;
                d[min(u, v)] ++;
            }
            else //删除 
            {
                if(d[min(u, v)]) //最小的死过 
                {
                    d[min(u, v)] --;
                    if(d[min(u,v)] == 0 && ans >= 1)//又活了 
                    ans --;
                }
            }
        }
        else
        {
            printf("%d\n", n - ans);
        }
    }
    return 0;
}