主席树

HDU6704 补
2019山东省赛 E 补

// 区间操作 灵活应用
静态区间第k小

普通权值线段树可以查询整体的第k小问题
而主席树就是利用这一点保存每个时刻的权值线段树，这样当查询区间第k值时就能通过相减得到这个区间的权值线段树 就相当于这个区间求整体第k值
故主席树能查询区间第k值(^__)

利用重复信息保存插入每个数时的 权值线段树
那么当求l~r的区间 时 只需要 将插入第r个数时的权值线段树T【root【r】】 减去T【root【l-1】】（其中的细节要好好理解）那么我们得到的其实就是L ~ R的权值线段树了 直接按步即可

主席树要注意内存 一般开正常大小25倍
代码参考qsc🙅

其中重点理解的应该还是怎么建立这个主席树的问题
当我们把所有数离散化后
如果在X位置插入一个数，那么我们对于新的主席树需要添加的边其实就是 从叶子X到根部ROOT的那一条链上面的点添加新边就可以了
原理其实挺好理解，难度应该在对于代码的理解与实现方面上（这应该也是所有数据结构的共同点）

巧妙的离散化（❓❓）不太重要记住就好 垃圾离散化1.28 只能使你的代码整洁一些，不建议使用

其中ROOT【i】代表的是第i个权值线段树 头结点的编号

代码中 update，query 中的参数X和Y其实都是一个节点的编号（困扰好久😞）
编号 编号 编号！！！

T[y].L即为左子树的编号 T【T【y】.L】.sum即为左子树的数字数量
其他类推

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define warn printf("!!**!!\n")
using namespace std;
typedef  long long L;
typedef pair<int,int>pii;
const int maxn=1e6;
const int mod=1e9+7;
const int oo=1e9;
const int N=100005;
int n,m,cnt,root[maxn*40+10],a[maxn*40+10],x,y,k;
struct node
{
    int l,r,sum;
} T[maxn*25+10];
vector<int>v;
int getid(int x)
{
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void update(int l,int r,int &x,int y,int pos)
{
    T[++cnt]=T[y],T[cnt].sum++,x=cnt;
    if(l==r)
        return;
    int mid=l+r>>1;
    if(mid>=pos)
        update(l,mid,T[x].l,T[y].l,pos);
    else
        update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r)
        return l;
    int mid=l+r>>1;
    ///编号 编号！！！
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    if(sum>=k)
        return query(l,mid,T[x].l,T[y].l,k);
    else
        return query(mid+1,r,T[x].r,T[y].r,k-sum);
}
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        cnt=0,v.clear();
        scanf("%d %d",&n,&m);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]),v.push_back(a[i]);

        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());

        for(int i=1; i<=n; i++)
            update(1,n,root[i],root[i-1],getid(a[i]));

        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d",&x,&y,&k);
            printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
        }
    }
}