主席树模版（自用）

例题：牛客网round58-随机化游戏时间

主席树中心思想：（发明者原话）“对于原序列的每一个前缀【1....i】建立出一颗线段树维护值域上每个数出现的次数，则其树是可减的”

对于题目给出的一系列数据，在数据本身的顺序下（编号顺序或建树dfs序）维护值域线段树，这样就可以在在一定的顺序下查询值域限制时的信息，如【l,r】值域下的第k小值，[l,r]下的子节点个数等。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include <sstream>
#include<map>
using namespace std;
#define int long long
//#define ll long long
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int tot = 0;
int root[N];
struct node {
    int sum = 0;
    int l = 0, r = 0;
}tr[N * 30];
#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)
#define sum(x) tr[x].sum
void pushup(int now) {
    sum(now) = sum(ls(now)) + sum(rs(now));
}
void upd(int last, int now, int pos, int k, int l, int r) {
    if (l == r) {
        sum(now) = sum(last) + k;
    }
    else {
        ls(now) = ls(last), rs(now) = rs(last);
        int mid = (l + r - 1) / 2; //处理l,r都是负数的情况
        if (pos <= mid) {
            ls(now) = ++tot;
            upd(ls(last), ls(now), pos, k, l, mid);
        }
        else {
            rs(now) = ++tot;
            upd(rs(last), rs(now), pos, k, mid + 1, r);
        }
        pushup(now);
    }
}
const int up = 1e9 + 5;
const int down = -(1e9 + 5);
void upd(int last, int now, int pos, int k) {
    upd(last, now, pos, k, down, up);
}

int kth(int last, int now, int k, int l, int r) {
    if (l == r)return l;
    int mid = (l + r - 1) / 2;
    int val = sum(ls(now)) - sum(ls(last));
    if (val >= k) {
        return kth(ls(last), ls(now), k, l, mid);
    }
    else {
        return kth(rs(last), rs(now), k - val, mid + 1, r);
    }
}
int kth(int last, int now, int k) {
    return kth(last, now, k, down, up);
}
int n, m, t;
int mod = 1e9 + 7;
int a[N];
int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
        b = b >> 1;
    }
    return res;
}
signed main() {
    cin >> t;
    while (t--) {
        tot = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            root[i] = ++tot;
            upd(root[i - 1], root[i], a[i], 1);
        }
        int d = 1;
        int u = n;
        for (int i = 1; i <= m; i++) {
            int l, r, k;
            cin >> l >> r >> k;
            if (k == r - l + 1) {
                d= d = max(d, kth(root[l - 1], root[r], k));
            }
            else if (k == 0) {
                u = min(u, kth(root[l - 1], root[r], k + 1) - 1);
            }
            else {
                d = max(d, kth(root[l - 1], root[r], k));
                u = min(u, kth(root[l - 1], root[r], k + 1) - 1);
            }
        }
        if (d == u) {
            cout << 1 << " " << d << "\n";
        }
        else {
            cout << qmi(u - d + 1, mod - 2) << "\n";
        }
    }
}