\(\mathtt{CF817E}\)

\(\mathcal{Description}\)

有 \(q\) 个操作\((1 \leq q \leq 10^{5})\)：

1、加入一个数 \(p_i(1 \leq p_i \leq 10 ^ 8)\)

2、删去一个数 \(p_i(1 \leq p_i \leq 10 ^ 8)\)

3、询问集合中有多少数异或 \(p_i\) 后的值小于 \(l_i(1 \leq p_i,l_i \leq 10 ^ 8)\)

\(\mathcal{Solution}\)

第三种操作询问异或后的值，于是自然而然可以想到用 \(01trie\)，所以可以把 \(p_i\) 插入到字典树内，\(1\) 操作是 \(+1\)，\(2\) 操作就是 \(-1\)，\(3\)操作询问是，把 \(p_i\) 的值遍历一遍，如果当前的位上是 \(0\)，把指针转到 \(p_j\) 的位上，否则加上这个位上的数，把指针转到另一边。

\(\mathcal{Code}\)

#include<bits/stdc++.h>

#define pow(x, i) (x >> i)

using namespace std;

const int N = 6e6 + 10, M = 30;

int cnt[N], trie[N][2], tot = 1, n;

inline int read() {

	int x = 0, k = 1; char c = getchar();

	for (; c < 48 || c > 57; c = getchar()) k ^= (c == '-');

	for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);

	return k ? x : -x;

}

inline void add(int x, int dg) {

    int p = 1;

    for (int i = M; i >= 0; --i) {

        if (dg == 1) trie[p][(pow(x, i) & 1)] = (trie[p][(pow(x, i) & 1)] != 0) ? trie[p][(pow(x, i) & 1)] : (++tot);

        p = trie[p][(pow(x, i) & 1)], cnt[p] += dg;

    }

}

inline int ask(int x, int y) {

    int p = 1;

    int sum = 0;

    for (int i = M; i >= 0; i--) {

        int t = (pow(y, i) & 1), t1 = (pow(x, i) & 1);

        if (t)

            sum += cnt[trie[p][t1]], p = trie[p][t1 ^ 1];

        else

            p = trie[p][t1];

    }

    return sum;

}

int main() {

    n = read();

    while (n--) {

        int opt = read(), x = read();

        if (opt == 1)

            add(x, 1);

        else if (opt == 2)

            add(x, -1);

        else if (opt == 3) {

            int y = read();

            printf("%d\n", ask(x, y));

        }

    }

    return 0;

}

巴特西

CF817E Choosing The Commander

\(\mathtt{CF817E}\)

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章