本文共 3284 字，大约阅读时间需要 10 分钟。

对于这个问题，我们可以使用一个双向链表结构来记录每个数的左右邻居，并结合并查集来维护这些邻居关系。具体来说，我们使用两个数组 L 和 R，分别记录每个数的最左边和最右边相邻的数。这样，当删除一个数时，只需要更新它左右邻居的指针即可。

解题思路

代码实现细节

#include 
   
    #include 
    
     using namespace std;#define ENDL "\n"typedef long long ll;const int inf = 0x3f3f3f3f;const int maxn = 5e5 + 10;const int Mod = 1e9 + 7;int n;int a[maxn], L[maxn], R[maxn], pre[maxn * 2];int tree[maxn << 2], size = 1;void build(int i, int l, int r) {    if (l == r) {        tree[i] = R[l];        return;    }    int mid = (l + r) >> 1;    int k = i << 1;    build(k, l, mid);    build(k | 1, mid + 1, r);    tree[i] = min(tree[k], tree[k | 1]);}void change(int i, int l, int r, int pos, int x) {    if (l == r) {        tree[i] = x;        return;    }    int mid = (l + r) >> 1;    int k = i << 1;    if (pos <= mid) {        change(k, l, mid, pos, x);    } else {        change(k | 1, mid + 1, r, pos, x);    }    tree[i] = min(tree[k], tree[k | 1]);}int query(int i, int l, int r, int x, int y) {    if (l == x && r == y) {        return tree[i];    }    int res = inf;    int mid = (l + r) >> 1;    int k = i << 1;    if (y <= mid) {        res = query(k, l, mid, x, y);    } else if (x > mid) {        res = query(k | 1, mid + 1, r, x, y);    } else {        int left = query(k, l, mid, x, mid);        int right = query(k | 1, mid + 1, r, mid + 1, y);        res = min(left, right);    }    return res;}int main() {    ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);    int q;    cin >> n >> q;    memset(pre, inf, sizeof pre);    for (int i = 1; i <= n; ++i) {        cin >> a[i];        if (pre[a[i]] != inf) {            L[i] = pre[a[i]];        } else {            L[i] = inf;        }        pre[a[i]] = i;    }    pre memset to inf;    for (int i = n; i >= 1; --i) {        if (pre[a[i]] != inf) {            R[i] = pre[a[i]];        } else {            R[i] = inf;        }        pre[a[i]] = i;    }    build(1, 1, n);    while (q--) {        int op;        cin >> op;        if (op == 1) {            int l;            cin >> l;            if (L[l] != inf) {                if (R[l] != inf) {                    int old = R[l];                    L[old] = inf;                    R[l] = inf;                }                if (L[l] != inf) {                    R[L[l]] = l;                }                if (R[l] != inf) {                    L[R[l]] = l;                }            }            L[l] = R[l] = inf;            change(1, 1, n, l, inf);        } else {            int l, r;            cin >> l >> r;            if (l > r) {                l = r;            }            int cur = query(1, 1, n, l, r);            if (cur != inf && l <= cur && cur <= r) {                cout << "1" << ENDL;            } else {                cout << "0" << ENDL;            }        }    }    return 0;}
    
   

代码解释

• 初始化：使用 L 和 R 数组记录每个数的左右邻居，pre 数组维护每个数的最近访问位置。
• 删除操作：更新数的左右邻居关系，并使用树状数组维护区间内的最大值。
• 查询操作：通过树状数组查找区间内的最大值，判断其是否在区间内，确定是否存在重复数。

这种方法高效地处理了大规模数据的操作，确保了在合理时间内完成查询和删除任务。

转载地址：http://ppqq.baihongyu.com/