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

对于这个问题，我们可以使用一个双向链表结构来记录每个数的左右邻居，并结合并查集来维护这些邻居关系。具体来说，我们使用两个数组 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/