标題效果：間隔可以改變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]);
}
}