主席树

全称为：可持久化线段树

我们考虑一件事情，如果说我们对于一个线段树来说，希望它可以查询一些修改之前的序列（我们称之为历史版本）

我们当然可以每一次把线段树复制一遍，但是时空复杂度并不能够接受

所以我们应该进行一些可持久化的处理：

我们发现对于单点修改来说，线段树最多改变的就是log2n个节点

所以我们可以把更改的几个节点单独拿出来存储起来，没有改变的部分就指向之前的节点，改变了就指向改变的节点

然后从根节点记录一下这是哪个历史版本（因为根节点一定会改变）

然后就没了

P3919 【模板】可持久化线段树 1（可持久化数组）

这个题是个板子

我们考虑，如果说对于一个数组来说，进行多次更改的复杂度为1，但是记录不同的状态就会变成n

那么主席树就可以把这些的复杂度均摊下来变成log2n对吧

然后就复杂度就变好了

就是个板子嘛过了过了

P3834 【模板】可持久化线段树 2

这个就比较经典（其实并不是很算板子的

我们考虑，静态区间第k小……

如果对于一个区间，我们把它放在桶里，是不是可以进行二分求出来第k小

那么线段树上二分是一个比较经典的套路：如果说权值线段树根节点的左端点数字个数大于等于k说明第k小的数字是在左端点的，否则就是右端点（懂了吧

我们就可以对于每一个都开一个线段树（但是并不是很优秀

那我们想到，如果说对于$[l,r]$的区间来说，如果说前面r个数字中有sum1个数字大于等于m，l个数字中有sum2个数字大于等于m，那么说明这个区间里面有sum1-sum2个数字大于等于m

那么我们就可以在主席树上面二分了

我们考虑在主席树上面存储上所有前缀的桶（当然要离散化）

然后再主席树上面二分答案就可以了

这个题还是挺不错的

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;

int n, m, q;
int lc[maxn << 5], rc[maxn << 5], cnt, val[maxn << 5], rt[maxn];
int change;
int a[maxn], b[maxn];

void build(int &rt, int l, int r)
{
    int mid = l + r >> 1;
    rt = ++cnt;
    if (l == r)
        return;
    build(lc[rt], l, mid);
    build(rc[rt], mid + 1, r);
    return;
}

int add(int lst, int l, int r)
{
    int rt = ++cnt;
    lc[rt] = lc[lst], rc[rt] = rc[lst], val[rt] = val[lst] + 1;
    if (l == r)
        return rt;
    int mid = l + r >> 1;
    if (change <= mid)
        lc[rt] = add(lc[rt], l, mid);
    else
        rc[rt] = add(rc[rt], mid + 1, r);
    return rt;
}

int ask(int L, int R, int l, int r, int k)
{
    int mid = l + r >> 1, x = val[lc[R]] - val[lc[L]];
    if (l == r)
        return l;
    if (x >= k)
        return ask(lc[L], lc[R], l, mid, k);
    return ask(rc[L], rc[R], mid + 1, r, k - x);
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - b - 1;
    build(rt[0], 1, m);
    for (int i = 1; i <= n; i++)
    {
        change = lower_bound(b + 1, b + 1 + m, a[i]) - b;
        rt[i] = add(rt[i - 1], 1, m);
    }
    while (q--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout << b[ask(rt[l - 1], rt[r], 1, m, k)] << endl;
    }
    return 0;
}

P2633 Count on a tree

这是一道非常经典的树上主席树的题目

首先我们考虑：如果对于一棵树上面两点间的路径来说，他们的路径可以说是他们各自到根的路径减去lca到根的路径再减去lca的父亲到根的路径

那么我们会发现，一个点到根的路径包含的权值在dfs的时候是可以权值主席树搞出来的（不过当然是需要离散化的了

既然这样直接二分就可以了

[P3168 CQOI2015]任务查询系统

这个就是一个板子题，如果说之前的主席树2是单点修改区间查询的话，这个就是区间修改单点查询

那么我们就可以把这个东西转化成一个差分上面前缀和的方式

对于每一个操作我们都把他转化成前端加后端减的操作就好了

P4559 [JSOI2018]列队

这个题由于什么排序不等式的东西（tbl题解）我们会发现，其实我们左边会有一部分的人向右跑，右边会有一部分人向左跑，并且相对顺序并不发生改变……

那么我们权值主席树存一下每一个前缀位置对应的人都在哪些位置

然后再主席树上面二分一下断点（左右跑的断点）然后用一些等差数列什么的东西求一下贡献

P3293 [SCOI2016]美味

我们会发现，这个题在某些意义上面和最大异或和还挺像的

还是像最大异或和一样从高位到低位考虑贡献贪心

我们考虑，如果说前面的几位已经考虑过了，是不是应该考虑这一位是不是有和这一位异或起来等于1的一位

就先把前面的几位答案搞出来，然后再权值主席树里面查找一下是不是有前面几位和答案一样，这意味不一样的数字，有的话这一位就可以变成1没有就不能

然后完了

P2839 [国家集训队]middle

又是一道调了一天的题啊（写主席树写多了一定要记住不是所有的主席树都是权值线段树

我们会发现，如果说一个数字是这个序列的中位数的话（在这道题中）（因为这个题里面偶数序列的中位数是两个数后面的一个

把所有的比中位数大的数字变成1，小于的变成-1，这个序列的和大于等于0

那么我们就可以二分这个中位数，然后再权值线段树上面找

我们会发现$[b,c]$这个区间里的所有数字必定选，其他的选前后缀

那么我们就在线段树上面找到区间和，区间最大前缀，区间最大后缀

然后合并check二分就好了