主席树

应用：

• 查询修改的历史性问题
• 查询第几大问题。

知识点：

• 值域线段树（每一个节点代表一个值域，储存在这个值域的数量（主席树要离散化））
• 将区间上的每一个点当成一个树，
• 在增添一个树的时候，树中有很多重复的地方，重复的地方就直接共用，新的地方就新增。

代码：

#include 
using namespace std;
#define ri register int
#define M 200005

template <class G> void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
 }

struct ddian{
    int l,r,lt,rt,tot;
}p[M<<5]; 

int tr[M];
int val[M],b[M];
int q;
int n,m;
int cent;
int build(int l,int r)
{
    int i=++cent;
    p[i].l=l;p[i].r=r;
    int mid=(l+r)>>1;
    if(l==r)
    {
        return i;
    }
    p[i].lt=build(l,mid);
    p[i].rt=build(mid+1,r);
    return i;    
}
int add(int o,int l,int r,int x)
{
    int ii=++cent;
    p[ii].l=l;p[ii].r=r;p[ii].lt=p[o].lt;p[ii].rt=p[o].rt;
    p[ii].tot=p[o].tot+1;
    if(l==r) return ii;
    int mid=(l+r)>>1;
    if(x<=mid)
    {
        p[ii].lt=add(p[ii].lt,l,mid,x);
    }
    else
    p[ii].rt=add(p[ii].rt,mid+1,r,x);
    return ii;
}
int qu(int v,int u,int x)
{
    int tmp=p[p[u].lt].tot-p[p[v].lt].tot;
    if(p[v].l==p[v].r)
    {
        return p[v].l;
    }
    if(tmp>=x)
    {
        return qu(p[v].lt,p[u].lt,x);
    }
    else
    {
        return qu(p[v].rt,p[u].rt,x-tmp);
    }
}
int main(){
    
    read(n);read(m);
    for(ri i=1;i<=n;i++)
     read(val[i]),b[i]=val[i];
     sort(b+1,b+1+n);
    q=unique(b+1,b+1+n)-b-1;
    tr[0]=build(1,q);
    
    for(ri i=1;i<=n;i++)
    {
        int x=lower_bound(b+1,b+1+q,val[i])-b;
        tr[i]=add(tr[i-1],1,q,x);
    }
    for(ri i=1;i<=m;i++)
    {
        int op[4];
        read(op[1]);read(op[2]);read(op[3]);
        int ans=qu(tr[op[1]-1],tr[op[2]],op[3]);   //
        printf("%d\n",b[ans]);
    }
    return 0;
    
}  

易写错的地方：

• 去重后的查找是 +q int x=lower_bound(b+1,b+1+q,val[i])-b;
• 是利用的前缀后，查询时 L-1;
• 是U-V，不是v-u