下标线段树(动态开点) + 值域平衡树(fhq threap)

如果想看堆存储的下标线段树 可以参考 滑稽 大佬的题解 orz

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

#define INF 2147483647

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];

// fhq  按照 值 去分
struct Node{
    int l, r;
    int val, key;
    int sz;
}fhq[N * 20];
int cnt;

int newnode(int val){
    fhq[ ++ cnt].val = val;
    fhq[cnt].key = rand();
    fhq[cnt].sz = 1;
    return cnt;
}

void pushup(int now){
    fhq[now].sz = fhq[fhq[now].l].sz + fhq[fhq[now].r].sz + 1;
}

void split(int now, int val, int &x, int &y){
    if(!now) x = y = 0;
    else{
        if(fhq[now].val <= val){
            x = now;
            split(fhq[now].r, val, fhq[now].r, y);
        }
        else{
            y = now;
            split(fhq[now].l, val, x, fhq[now].l);
        }
        pushup(now);
    }
}

int merge(int x,int y){
    if(!x || !y) return x + y;
    if(fhq[x].key > fhq[y].key){
        fhq[x].r = merge(fhq[x].r, y);
        pushup(x);
        return x;
    }
    else{
        fhq[y].l = merge(x, fhq[y].l);
        pushup(y);
        return y;
    }
}
int x, y, z;
void ins(int &root, int val){
    split(root, val, x, y);
    root = merge(merge(x, newnode(val)), y);
}
void del(int &root, int val){
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(fhq[y].l, fhq[y].r);
    root = merge(merge(x, y), z);
}
int getrank(int &root, int val){
    split(root, val - 1, x, y);
    int t = fhq[x].sz;
    root = merge(x,y);
    return t;
}
int getnum(int &root,int rank){
    int now = root;
    while(now){
        if(fhq[fhq[now].l].sz + 1 == rank)
            break;
        else if(fhq[fhq[now].l].sz >= rank)
            now = fhq[now].l;
        else{
            rank -= fhq[fhq[now].l].sz + 1;
            now = fhq[now].r;
        }
    }
    return fhq[now].val;
}
int get_prev(int &root, int val){
    split(root, val - 1, x, y);
    int u = x;
    while(fhq[u].r)  u = fhq[u].r;
    int res = fhq[u].val;
    root = merge(x, y);
    return res;
}

int get_next(int &root, int val){
    split(root, val, x, y);
    int u = y;
    while(fhq[u].l)  u = fhq[u].l;
    int res = fhq[u].val;
    root = merge(x, y);
    return res;
}
void ldr(int now){
    if(!now) return;
    ldr(fhq[now].l);
    cerr << fhq[now].val << ' ';
    ldr(fhq[now].r);
}
// sgt 下标线段树
struct Nd{
    int l, r;
    int rt;
    int lc, rc;
}sgt[N << 1];
int tot, sgtrt;

int newsgt(int l,int r){
    sgt[ ++ tot].l = l, sgt[tot].r = r;
    sgt[tot].lc = 0;
    sgt[tot].rc = 0;
    sgt[tot].rt = 0;
    return tot;
}
void build(int &now, int l,int r){
    if(!now) now = newsgt(l, r);
    for(int i = l;i <= r;i ++ ){
        ins(sgt[now].rt, a[i]);
    }
    // ldr(sgt[now].rt);
    if(l == r) return ;
    int mid = l + r >> 1;
    build(sgt[now].lc, l, mid);
    build(sgt[now].rc, mid + 1, r);
}

void update(int &now,int pos,int val){
    ins(sgt[now].rt, val);
    del(sgt[now].rt, a[pos]);
    if(sgt[now].l == sgt[now].r) return ;
    int mid = sgt[now].l + sgt[now].r >> 1;
    if(pos <= mid) update(sgt[now].lc, pos, val);
    else update(sgt[now].rc, pos, val);
}

int qRank(int &now,int l,int r,int x){
    if(sgt[now].l >= l && sgt[now].r <= r)
        return getrank(sgt[now].rt, x);
    int mid = sgt[now].l + sgt[now].r >> 1;
    int res = 0;
    if(l <= mid) res = qRank(sgt[now].lc, l, r, x);
    if(r > mid) res += qRank(sgt[now].rc, l, r, x);
    return res;
}
int qkth(int l,int r,int k){
    int lg = 0, rg = 1e8;
    while(lg < rg){
        int mid = lg + rg + 1 >> 1;
        if(qRank(sgtrt, l, r, mid) < k)  lg = mid;
        else  rg = mid - 1;
    }
    return rg;
}
int query_prev(int &now, int l, int r, int val){
    if(sgt[now].l >= l && sgt[now].r <= r){
        return get_prev(sgt[now].rt, val);
    }
    int mid = sgt[now].l + sgt[now].r >> 1, res = -1;
    if(l <= mid)  res = query_prev(sgt[now].lc, l, r, val);
    if(r > mid)  res = max(res, query_prev(sgt[now].rc, l, r, val));
    return res;
}

int query_next(int &now, int l, int r, int val){
    if(sgt[now].l >= l && sgt[now].r <= r)  return get_next(sgt[now].rt, val);

    int mid = sgt[now].l + sgt[now].r >> 1, res = -1;
    if(l <= mid)  res = query_next(sgt[now].lc, l, r, val);
    if(r > mid){
        int t = query_next(sgt[now].rc, l, r, val);
        if(res == -1 || t != -1 && t < res)  res = t;
    }
    return res;
}
int main(){

    // 一定要初始化这个   因为 会查到不存在的val 需要特判
    fhq[0].val = -1;
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);

    build(sgtrt, 1, n);
    while(m -- ){
        int op, l, r, k, val, t;
        scanf("%d", &op);
        switch(op){
            case 1:
                scanf("%d%d%d", &l, &r, &val);
                printf("%d\n", qRank(sgtrt, l, r, val) + 1);
                break;
            case 2:
                scanf("%d%d%d", &l, &r, &k);
                printf("%d\n", qkth(l, r, k));
                break;
            case 3:
                scanf("%d%d", &k, &val);
                update(sgtrt, k, val);
                a[k] = val;
                break;
            case 4:
                scanf("%d%d%d", &l, &r, &val);
                t = query_prev(sgtrt, l, r, val);
                if(t == -1)  t = -INF;
                printf("%d\n", t);
                break;
            case 5:
                scanf("%d%d%d", &l, &r, &val);
                t = query_next(sgtrt, l, r, val);
                if(t == -1)  t = INF;
                printf("%d\n", t);
                break;
        }
    }
    return 0;
}