ABC278C 题解

_dijkstra_ · 2022-11-21 09:31:41 · 题解

整合题解。

为什么我每次都会将 C 题做得很复杂呢。

思路

由于用户编号很大，所以我们要离散化。

显然，最多只会出现 2 \times q 种编号，所以离散化后也只有这么多个数。

然后暴力即可。这里你想用什么就用什么，比如我用了 set。

代码

省去了大段的缺省源。

const int N = 4e5 + 5;
int op[N], a[N], b[N];
int t[N], m, cur;
int calc(int x) {return lower_bound(t + 1, t + m + 1, x) - t;}
void solve()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d%d", &op[i], &a[i], &b[i]);
        t[++cur] = a[i], t[++cur] = b[i];
    }
    sort(t + 1, t + cur + 1); //离散化
    m = unique(t + 1, t + cur + 1) - t;

    set <int> st[N << 1];
    for (int i = 1; i <= q; i++) //暴力计算答案
    {
        a[i] = calc(a[i]), b[i] = calc(b[i]);
        if (op[i] == 1) st[a[i]].insert(b[i]);
        else if (op[i] == 2) st[a[i]].erase(b[i]);
        else
        {
            if (st[a[i]].count(b[i]) && st[b[i]].count(a[i])) puts("Yes");
            else puts("No");
        }
    }
}