主席树

OI&ACM, 可持久化数据结构
  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谈谈各种数据结构
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);
	}
}
主席树