可持久化线段树总结

可持久化线段树的总结
-----by石门中学柯新宇
可持久化线段树，说白了，就是具有一个个时间的树链。因为修改单点，只会对树上的一条链发生改变，我们只需记录更改过的树链即可。

我们可以发现，每次修改单点时，只会影响到一条链，只需把链存起来就行了。

我才用的方法是：对于每一次修改，开一个root[]，记录树根。（用指针类型，写起来比较方便）

structnode{long long s,d; node *left,*right;}tree[(maxn<<5)+(maxn<<3)],*root[maxn];

node*newnode()
{
t0++;tree[t0].s=tree[t0].d=0;
tree[t0].left=tree[t0].right=tree;
returntree+t0;

}

root[0]=newnode();
for(inti=1;i<=ti;i++) root[i]=newnode();
for(inti=1;i<=ti;i++)
{
*root[i]=*root[i-1];
updata(root[i],1,lenN,……);
……

}

每一次updata()时要新开节点来储存信息，现将原信息复制给新节点，再做修改。过程如下：

voidupdata(node *ro,int L,int R,int x,long long v) {
if(L==R){ro->d++;ro->s+=v;return;}
intmid=(L+R)>>1;
node*yy=newnode(); //新开节点
if(x<=mid)
{

//拷贝原来的信息
//将新的节点连给父亲结点

updata(ro->left,L,mid,x,v);
}else
{
*yy=*ro->right;
ro->right=yy;
updata(ro->right,mid+1,R,x,v);
}
ro->s=ro->left->s+ro->right->s; //up操作 ro->d=ro->left->d+ro->right->d;
}

至于，区间修改，开个懒惰标记记一记就好了，不用每次更新都下发标记（这样会爆空间的），查询的时候加上祖先的标记就好了。

有几道比较经典的题，可以用来练练手：
先把可持久化线段树模板练熟了，做题会事半功倍。

------------------因为这都是“套路”
Bzoj2588-----比较麻烦，离散化加lca加query(r1,r2,r3,r4,1,n,……)Bzoj2809-----离散化
Hdu5919
Hdu4348

Bzoj2809代码：
#include<cstdio>
#include<algorithm>

#defineimin(a,b) ((a<b)?a:b)
#definemaxn 100050

usingnamespace std;

intn,m,t0,ti;
longlong ans;
intfa[maxn],ll[maxn];
longlong cct[maxn];
structaaaa{int l,r,d;} tm[maxn];
structnode{long long s,d; node *left,*right;}tree[(maxn<<5)+(maxn<<3)],*root[maxn];
structeeee{int fa,pi; long long ci,li; } mas[maxn]; inth[maxn],d0;
structdata{int to,next;} d[maxn];

node*newnode()

{
t0++;tree[t0].s=tree[t0].d=0;
tree[t0].left=tree[t0].right=tree;
returntree+t0;
}

boolcmp(int A,int B)
{
return(mas[A].ci<mas[B].ci);
}

voidaddedge(int fr,int to)
{
d0++;d[d0].to=to; d[d0].next=h[fr]; h[fr]=d0; }

voiddfs(int x)
{
intyu=++ti;tm[ti].l=ti;tm[ti].d=x;
for(intp=h[x];p>0;p=d[p].next) dfs(d[p].to); tm[yu].r=ti;
}

voidupdata(node *ro,int L,int R,int x,long long v) {
if(L==R){ro->d++;ro->s+=v;return;}
intmid=(L+R)>>1;
node*yy=newnode();
if(x<=mid)
{
*yy=*ro->left;
ro->left=yy;
updata(ro->left,L,mid,x,v);
}else
{
*yy=*ro->right;
ro->right=yy;
updata(ro->right,mid+1,R,x,v);
}
ro->s=ro->left->s+ro->right->s;
ro->d=ro->left->d+ro->right->d;
}

longlong query(node *r1,node *r2,int L,int R,long long M)

{
if(L==R)return imin((r2->d-r1->d),M/cct[L]);
if(r2->s-r1->s<=M)return r2->d-r1->d;
longlong xx=r2->left->s-r1->left->s;
intmid=(L+R)>>1;
if(xx>=M)return query(r1->left,r2->left,L,mid,M); else return
(r2->left->d-r1->left->d+query(r1->right,r2->right,mid+1,R,M-xx)); }

intmain()
{
scanf("%d%d",&n,&m);
mas[0].li=0;ti=0;
tree[0].left=tree[0].right=tree;
for(inti=1;i<=n;i++)
{
scanf("%d%lld%lld",&mas[i].fa,&mas[i].ci,&mas[i].li); ll[i]=i;addedge(mas[i].fa,i);
}
sort(ll+1,ll+1+n,cmp);
intlast=-1,y0=0;

for(inti=1;i<=n;i++)
{
if(last!=mas[ll[i]].ci)
{
y0++;last=mas[ll[i]].ci;
cct[y0]=mas[ll[i]].ci;
}
mas[ll[i]].pi=y0;
}
ti=-1;
dfs(0);
root[0]=newnode();
for(inti=1;i<=ti;i++) root[i]=newnode();
for(inti=1;i<=ti;i++)
{
*root[i]=*root[i-1];
updata(root[i],1,y0,mas[tm[i].d].pi,mas[tm[i].d].ci);
}
ans=0;
for(inti=1;i<=n;i++)
{
longlong num=query(root[tm[i].l-1],root[tm[i].r],1,y0,m);

ans=(num*mas[tm[i].d].li>ans)?num*mas[tm[i].d].li:ans; }
printf("%lld\n",ans);
}

4408:[Fjoi 2016]神秘数
TimeLimit: 10 Sec Memory Limit: 128 MB
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，
1= 1
2= 1+1
3= 1+1+1
4= 4
5= 4+1
6= 4+1+1
7= 4+1+1+1
8无法表示为集合S的子集的和，故集合S的神秘数为8。

现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Input
第一行一个整数n，表示数字个数。

第二行n个整数，从1编号。

第三行一个整数m，表示询问个数。

以下m行，每行一对整数l,r，表示一个询问。

Output
对于每个询问，输出一行对应的答案。

SampleInput
5
12 4 9 10
5
11
12
13
14
15
SampleOutput
2
4
8
8
8
对于100%的数据点，n,m<= 100000，∑a[i]<= 10^9

注：很有趣的题，建议不要一开始就看题解，仔细想一想。

AC代码：
#include<cstdio>
#include<algorithm>

#definemaxn 100050
#defineFor(a,b,c) for(int a=b;a<=c;a++)

usingnamespace std;

intn,m0,m,t0;
intd[maxn],mp[maxn];

structdata
{
data*left,*right;
intsum;
}tree[80*maxn],*root[maxn];

boolcmp(int a,int b)
{
return(d[a]<d[b]);

}

data*newnode()
{
t0++;
tree[t0].left=tree[t0].right=tree;
tree[t0].sum=0;
returntree+t0;
}

voidupdata(data *ro,int L,int R,int x,int vv) {
if(L>x|| R<x) return;
if(L==x&& R==x)
{
ro->sum+=vv;
return;
}
intmid=(L+R)>>1;
data*yy=newnode();
if(x<=mid)
{

*yy=*ro->left;
ro->left=yy;
updata(ro->left,L,mid,x,vv);
}else
{
*yy=*ro->right;
ro->right=yy;
updata(ro->right,mid+1,R,x,vv);
}
ro->sum=ro->left->sum+ro->right->sum;}

intquery(data *r1,data *r2,int L,int R,int li,int ri) {
if(li>R|| ri<L) return 0;
if(li<=L&& R<=ri) return (r2->sum-r1->sum); intmid=(L+R)>>1;
intx1=query(r1->left,r2->left,L,mid,li,ri);
intx2=query(r1->right,r2->right,mid+1,R,li,ri); return(x1+x2);
}

intmain()
{
scanf("%d",&n);
For(i,1,n)scanf("%d",&d[i]),mp[i]=i; d[n+1]=1e9;
sort(mp+1,mp+1+n,cmp);
intoi=0,p=0;
For(i,1,n)
{
oi=(p<d[mp[i]])?oi+1:oi;
p=d[mp[i]];
mp[i]=oi;
}
m0=oi;
scanf("%d",&m);
tree[0].left=tree[0].right=tree;
for(inti=1;i<=n;i++) root[i]=newnode(); root[0]=&tree[0];
For(ti,1,n)
{
*root[ti]=*root[ti-1];
updata(root[ti],1,m0,mp[ti],d[ti]);

}
For(i,1,m)
{
intll,rr;
scanf("%d%d",&ll,&rr);
intlose=1,he=0;
for(;;)
{
intl=0,r=n+1;
while(l+1<r)
{
intmm=(l+r)>>1;
if(d[mm]<=lose)l=mm; else r=mm; }
he=query(root[ll-1],root[rr],1,m0,1,mp[l]); if(he<lose)break;
lose=he+1;
}
printf("%d\n",lose);
}
}

思路：假设现在可以构造[1..X]，如果加入了一个A(A<=X+1)，那么，一定可以构造[1..X+A]。反之，会出现断层，构造不了X+1，就输出X+1就行了。

原问题变为L..R中，求最小的X，使得∑A[i]（A[i]<X）<X成立。