主席树

  1. 1 【poj 2104】K-th Number
  2. 2 【bzoj 3524】[Poi2014]Couriers【bzoj 2223】[Coci 2009]PATULJCI
  3. 3 【bzoj 1901】[Zju2112] Dynamic Rankings
  4. 4 【bzoj 3932】[CQOI2015]任务查询系统

参考
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。
一些数据结构,比如线段树或平衡树,他们一般是要么维护每个元素在原序列中的排列顺序,要么是维护每个元素的大小顺序,若是像二者兼得。。(反正我是觉得很。。)那么,这道题就想想主席树吧~

比如求区间第k小(poj 2104)
其实相当于建n棵线段树
比如一棵线段树,记为tree[i][j],表示区间[i,j]的线段树。那么,要得到它的情况,可以利用另外两棵树,tree[1][i-1]和tree[1][j],得出来。也就是说,可以由建树的一系列历史版本推出。

那么,怎么创建这些树呢?
首先,离散化数据。因为如果数据太大的话,线段树会爆~~

在所有树中,是按照当前区间元素的离散值(也就是用大小排序)储存的,在每个节点,存的是这个区间每个元素出现的次数之和(size)。出现的次数,也就是存了多少数进来(建树时,是一个数一个数地存进来的)。
先建一棵线段树,所有的节点size为0,再一个节点一个节点地添加。把每个数按照自己的离散值,放到树中合适的位置,路径上size+1。当然,不能放到前一棵树中,要重新建树。第i棵树存的是区间(原序列)[1,i]。但是,如果是这样,那么会MLE+TLE。因此,要充分利用历史版本。
用两个指针,分指当前空树和前一棵树。因为每棵树的结构是一样的,只是里面的size不同,但是两棵相邻的树,只有一数只差,因此,如果元素要进左子树的话,右子树就会跟上个树这个区间的右子树是完全一样的,因此,可以直接将本树本节点的右子树指针接到上棵树当前节点的右儿子,这样即省时间,又省空间。
每添加一个节点(也就是新建一棵树)的复杂度是O(logn)。

建完之后,要怎么查找呢?
跟一般的在整棵树中找第k个数是一样的。对于第i-1棵和第j棵线段树(i<=j),在同一节点上(两节点所表示的区间相同),size之差表示的是,原序列区间[i,j]在当前节点所表示的区间里,出现多少次(有多少数的大小是在这个区间里的)。同理,对于同一节点,如果在两棵树中,它们的左权值之差大于等于k,那么要求的数就在左孩子,否则在右孩子。当定位到叶子节点时,就可以输出了。

from范浩强_wc2012谈谈各种数据结构

1 【poj 2104】K-th Number

给定一个序列,询问某一个区间内第k小的值

见上面的解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
int n,m,totn,a[100001],b[100001];
int sz,root[100001],s[2000000],ls[2000000],rs[2000000];
void Insert(int l,int r,int x,int &y,int v)
{
y=++sz;
s[y]=s[x]+1;
if(l==r) return;
ls[y]=ls[x]; rs[y]=rs[x];
int mid=(l+r)>>1;
if(v<=mid) Insert(l,mid,ls[x],ls[y],v);
else Insert(mid+1,r,rs[x],rs[y],v);
}
int Ask(int l,int r,int x,int y,int k)
{
if(l==r) return l;
int mid=(l+r)>>1,v=s[ls[y]]-s[ls[x]];
if(v>=k) return Ask(l,mid,ls[x],ls[y],k);
else return Ask(mid+1,r,rs[x],rs[y],k-v);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
totn=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
Insert(1,totn,root[i-1],root[i],lower_bound(b+1,b+totn+1,a[i])-b);
for(int i=1,x,y,z;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),
printf("%d\n",b[Ask(1,totn,root[x-1],root[y],z)]);
}

2 【bzoj 3524】[Poi2014]Couriers【bzoj 2223】[Coci 2009]PATULJCI

给一个长度为n的序列a。1≤a[i]≤n。
m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。

因为1≤a[i]≤n,所以不用离散化了,2333
size记录某一个值出现的次数,如果有大于(r-l+1)/2的输出就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
using namespace std;
const int N=500001;
int n,m,cnt,root[N],size[N*20],ls[N*20],rs[N*20];
void Insert(int l,int r,int x,int &y,int v)
{
y=++cnt;
size[y]=size[x]+1;
if(l==r) return;
ls[y]=ls[x]; rs[y]=rs[x];
int mid=(l+r)>>1;
if(v<=mid) Insert(l,mid,ls[x],ls[y],v);
else Insert(mid+1,r,rs[x],rs[y],v);
}
int Quary(int l,int r,int x,int y,int v)
{
if(l==r) return l;
int mid=(l+r)>>1;
if(size[ls[y]]-size[ls[x]]>v) return Quary(l,mid,ls[x],ls[y],v);
if(size[rs[y]]-size[rs[x]]>v) return Quary(mid+1,r,rs[x],rs[y],v);
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++)
scanf("%d",&x),Insert(1,n,root[i-1],root[i],x);
for(int i=1,x,y;i<=m;i++)
scanf("%d%d",&x,&y),
printf("%d\n",Quary(1,n,root[x-1],root[y],(y-x+1)>>1));
}

3 【bzoj 1901】[Zju2112] Dynamic Rankings

动态区间第k小,即可修改某点的值,可询问某区间的第k小

树状数组+主席树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=10001;
int n,m,tot,totn,totx,toty,a[N],b[N*2],A[N],B[N],C[N];
int X[15],Y[15],root[N],size[N*600],ls[N*600],rs[N*600];
char s[3];
void Insert(int l,int r,int x,int &y,int k,int v)
{
y=++tot;
size[y]=size[x]+v;
ls[y]=ls[x];rs[y]=rs[x];
if(l==r) return;
int mid=(l+r)>>1;
if(k<=mid) Insert(l,mid,ls[x],ls[y],k,v);
else Insert(mid+1,r,rs[x],rs[y],k,v);
}
int Quary(int l,int r,int k)
{
if(l==r) return l;
int sum=0,mid=(l+r)>>1;
for(int i=1;i<=totx;i++) sum-=size[ls[X[i]]];
for(int i=1;i<=toty;i++) sum+=size[ls[Y[i]]];
if(k<=sum)
{
for(int i=1;i<=totx;i++) X[i]=ls[X[i]];
for(int i=1;i<=toty;i++) Y[i]=ls[Y[i]];
return Quary(l,mid,k);
}
else
{
for(int i=1;i<=totx;i++) X[i]=rs[X[i]];
for(int i=1;i<=toty;i++) Y[i]=rs[Y[i]];
return Quary(mid+1,r,k-sum);
}
}
void Add(int x,int v)
{
int k=lower_bound(b+1,b+totn+1,a[x])-b;
for(int i=x;i<=n;i+=i&(-i))
Insert(1,totn,root[i],root[i],k,v);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[++totn]=a[i];
for(int i=1;i<=m;i++)
{
scanf("%s%d%d",s,&A[i],&B[i]);
if(s[0]=='Q') scanf("%d",&C[i]);
else b[++totn]=B[i];
}
sort(b+1,b+totn+1);
totn=unique(b+1,b+totn+1)-b-1;
for(int i=1;i<=n;i++) Add(i,1);
for(int i=1;i<=m;i++)
if(C[i])
{
totx=toty=0;
for(int j=A[i]-1;j;j-=j&(-j)) X[++totx]=root[j];
for(int j=B[i];j;j-=j&(-j)) Y[++toty]=root[j];
printf("%d\n",b[Quary(1,totn,C[i])]);
}
else Add(A[i],-1),a[A[i]]=B[i],Add(A[i],1);
}

4 【bzoj 3932】[CQOI2015]任务查询系统

超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<algorithm>
#include<vector>
#include<cstdio>
#define N 5000000
using namespace std;
int n,m,pre=1,totn,b[100001],root[100001];
int sz,ls[N],rs[N],size[N],sum[N];
vector<int> a[100005];
void Insert(int l,int r,int x,int &y,int k,int v)
{
y=++sz;ls[y]=ls[x];rs[y]=rs[x];
size[y]=size[x]+v;sum[y]=sum[x]+b[k]*v;
if(l==r) return;
int mid=(l+r)>>1;
if(k<=mid) Insert(l,mid,ls[x],ls[y],k,v);
else Insert(mid+1,r,rs[x],rs[y],k,v);
}
int Quary(int l,int r,int x,int k)
{
if(k>=size[x]) return sum[x];
if(l==r) return sum[x]/size[x]*k;
int mid=(l+r)>>1,ans=Quary(l,mid,ls[x],k);
if(k>size[ls[x]]) ans+=Quary(mid+1,r,rs[x],k-size[ls[x]]);
return ans;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1,s,e,p;i<=m;i++)
{
scanf("%d%d%d",&s,&e,&p);
a[s].push_back(p);
a[e+1].push_back(-p);
b[i]=p;
}
sort(b+1,b+m+1);
totn=unique(b+1,b+m+1)-b-1;
for(int i=1,t;i<=n;i++)
{
root[i]=root[i-1];
for(int j=0;j<a[i].size();j++)
{
int tag=1;
if(a[i][j]<0) tag=-1,a[i][j]=-a[i][j];
Insert(1,totn,root[i],root[i],lower_bound(b+1,b+totn+1,a[i][j])-b,tag);
}
}
for(int i=1,X,A,B,C;i<=n;i++)
{
scanf("%d%d%d%d",&X,&A,&B,&C);
pre=Quary(1,totn,root[X],1+((long long)A*pre+B)%C);
printf("%d\n",pre);
}
}