poj2104 K-th Number区间第k小值 主席树

原来主席树就是可持久化线段树啊，刚知道，，，

作为一道裸题，还是必A的，然而一开始偷懒不写离散化跪了N多遍，后来在缪大的帮助下发现了这个问题，遂A之

——又是这种破问题，实在不想说自己了

把n个数看成n次修改，对于每一次都建线段树，于是就能得到N棵线段树

然后时间空间全都爆炸，我们得到了完美的程序

但是每次因为只修一个叶子，所以只有一条根到叶的节点被修改，只要把这一部分备份一份就好了

最后返回新的根，用于保存

最后求的时候只要把两端点（左端点-1）的线段树上的点权值一减就搞定了

代码难看的要死，离散化是后来加的，看得出加的很生硬

#include <cstdio>
#include <algorithm>
#define INF 2000000000
#define max n
#define min 1
using namespace std;
struct node
{
    int val,ls,rs;
} t[10000000];
int cnt=0;
struct num
{
    int val,ran,rea;
} a[2000000];
bool operator<(num a,num b)
{
    return a.val<b.val;
}
bool com(num a,num b)
{
    return a.ran<b.ran;
}
int root[2000000],dui[2000000];
int add(int now,int l,int r,int x)
{
    int ne=++cnt,mid=(l+r)/2;
    t[ne]=t[now];
    t[ne].val++;
    if(l<r)
    if(x<=mid)
        t[ne].ls=add(t[now].ls,l,mid,x);
    else
        t[ne].rs=add(t[now].rs,mid+1,r,x);
    return ne;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].ran=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        a[i].rea=i;
        dui[a[i].rea]=a[i].val;
    }
    sort(a+1,a+n+1,com);
    for(int i=1;i<=n;i++)
        root[i]=add(root[i-1],min,max,a[i].rea);
    for(int i=1;i<=m;i++)
    {
        int x,y,z,l,r,mid;
        scanf("%d%d%d",&x,&y,&z);
        for(x=root[x-1],y=root[y],l=min,r=max,mid=(l+r)/2;l<r;mid=(l+r)/2)
        if(t[t[y].ls].val-t[t[x].ls].val<z)
        {
            z-=t[t[y].ls].val-t[t[x].ls].val;
            x=t[x].rs;y=t[y].rs;
            l=mid+1;
        }
        else
        {
            x=t[x].ls;y=t[y].ls;
            r=mid;
        }
        printf("%d
",dui[l]);
    }
    return 0;
}