两种操作，一种单点赋值，一种求区间有没有重复的数字

值域 1e6, $n,m$ 1e5

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10, INF = 1e8;
int n;
struct Node{
    int l, r;
    int key, val;
    int cnt, s; 
}tr[N];

int root, idx;

void pushup(int p) {
    tr[p].s = tr[tr[p].l].s + tr[tr[p].r].s + tr[p].cnt;
}

int get_node(int key) {
    tr[ ++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].s = 1;
    return idx;
}

void zig(int &p) {
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int &p) {
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

void remove(int &p, int key) {
    if (!p) return;
    if (tr[p].key == key) {
        if (tr[p].cnt > 1) tr[p].cnt --;
        else if (tr[p].l || tr[p].r) {
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                zig(p);
                remove(tr[p].r, key);
            }
            else {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if (tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);
    pushup(p);
}

void insert(int &p, int key) {
    if (!p) p = get_node(key);
    else if (tr[p].key == key) tr[p].cnt ++;
    else if (tr[p].key > key) {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

void build() {
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);
}

int get_rk(int &p, int key) {
    if (!p) return 0;
    if (tr[p].key == key) return tr[tr[p].l].s + 1;
    if (tr[p].key > key) return get_rk(tr[p].l, key);
    else return tr[tr[p].l].s + tr[p].cnt + get_rk(tr[p].r, key);
}

int get_key(int &p, int rank) {
    if (!p) return INF;
    if (tr[tr[p].l].s >= rank) return get_key(tr[p].l, rank);
    if (tr[p].cnt + tr[tr[p].l].s >= rank) return tr[p].key;
    return get_key(tr[p].r, rank - tr[tr[p].l].s - tr[p].cnt);

}

int get_prev(int &p, int key) {
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int &p, int key) {
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main() {
    build();
    cin >> n;
    while (n -- ) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove(root, x);
        else if (opt == 3) cout << get_rk(root, x)  - 1 << endl;
        else if (opt == 4) cout << get_key(root, x + 1) << endl;
        else if (opt == 5) cout << get_prev(root, x) << endl;
        else cout << get_next(root, x) << endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
struct D{
    int a, b, c, x;
    int res;
    bool operator< (const D& t) const {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const D& t) const {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[M];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)  // 返回前x个数的和
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void merge_sort(int l, int r)  // 归并排序
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i].b <= q[j].b)
            add(q[i].c, q[i].x), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    while (i <= mid) add(q[i].c, q[i].x), w[k ++ ] = q[i ++ ];
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].x);
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}


int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);

    int k = 1;
    for (int i = 1; i < n; i ++ )
        if (q[i] == q[k - 1]) q[k - 1].x ++;
        else q[k ++ ] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i ++ )
        ans[q[i].res + q[i].x - 1] += q[i].x;

    for (int i = 0; i < n; i ++ )
        printf("%d\n", ans[i]);
    return 0;
}