标题效果：间隔可以改变k少

我的两个天树牌主席。。。

隔断Count On A Tree 之后我一直认为，随着树的主席的变化是分域林木覆盖率可持久段树。

。。

事实上，我是误导。。。

尼可持久化线段树毛关系都木有啊！！

！

那就是动态的权值线段树啊啊啊啊啊啊啊！！！

好吧这里给不明确主席树的孩纸一些简单介绍：

1.外层树状数组

2.里层线段树

3.线段树动态开节点。仅此而已。和可持久化全然没关系。

4.一个点上的线段树和其它版本号毛关系都没有。

5.正常依照普通的树套树往里插即可了。

7.询问时把log个线段树放在一起跑(不要看我的代码，我的代码写的是log^3的)

8.节点数是nlog^2n

9.看题解要专心。没有第六点你看到了么。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 10100

using namespace std;

struct Tree{

    Tree *ls,*rs;

    int num;

}*tree[M],mempool[2002002],*C=mempool;

int n,m,a[M];

void Insert(Tree*&p,int x,int y,int val)

{

    int mid=x+y>>1;

    if(!p) p=C++;

    p->num++;

    if(x==y)

        return ;

    if(val<=mid)

        Insert(p->ls,x,mid,val);

    else

        Insert(p->rs,mid+1,y,val);

}

void Delete(Tree*&p,int x,int y,int val)

{

    int mid=x+y>>1;

    p->num--;

    if(x==y)

        return ;

    if(val<=mid)

        Delete(p->ls,x,mid,val);

    else

        Delete(p->rs,mid+1,y,val);

}

int Get_Ans(Tree*p,int x,int y,int val)

{

    int mid=x+y>>1;

    if(!p)

        return 0;

    if(!p->num)

        return 0;

    if(x==y)

        return p->num;

    if(val<=mid)

        return Get_Ans(p->ls,x,mid,val);

    else

        return (p->ls?p->ls->num:0) + Get_Ans(p->rs,mid+1,y,val);

}

void Update(int x,int y)

{

    for(;x<=n;x+=x&-x)

        Insert(tree[x],0,1000000000,y);

}

void Downdate(int x,int y)

{

    for(;x<=n;x+=x&-x)

        Delete(tree[x],0,1000000000,y);

}

int Get_Ans(int x,int y)

{

    int re=0;

    for(;x;x-=x&-x)

        re+=Get_Ans(tree[x],0,1000000000,y);

    return re;

}

int Bisection(int x,int y,int k)

{

    int l=0,r=1000000000;

    while(l+1<r)

    {

        int mid=l+r>>1;

        if( Get_Ans(y,mid) - Get_Ans(x-1,mid) >= k )

            r=mid;

        else

            l=mid;

    }

    if( Get_Ans(y,l) - Get_Ans(x-1,l) >= k )

        return l;

    return r;

}

int main()

{

    int i,x,y,k;

    char p[10];

    cin>>n>>m;

    for(i=1;i<=n;i++)

        scanf("%d",&a[i]),Update(i,a[i]);

    for(i=1;i<=m;i++)

    {

        scanf("%s",p);

        if(p[0]=='Q')

            scanf("%d%d%d",&x,&y,&k),printf("%d\n", Bisection(x,y,k) );

        else

            scanf("%d%d",&x,&y),Downdate(x,a[x]),a[x]=y,Update(x,a[x]);

    }

}