可持久化线段树练习（一）_可持久化线段树题单

题目一：bzoj 3524（模板题）

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

依旧是权值线段树+可持久化的组合。也算主席树模板题吧，权当练手。

因为一个区间只有一个数的次数大于(r-l+1)/2，所以相当于单点查询

#define mid     (l+r>>1)
const int maxn=1e5+7;
int n,m,a[maxn];
int tot=0,rt[maxn];
struct node{	int l,r,num;	}t[maxn<<5];
void update(int &i,int l,int r,int pre,int x){
	i=++tot;	t[i]=t[pre];	t[i].num++;
	if(l==r)	return;
	if(x<=mid)	update(t[i].l,l,mid,t[pre].l,x);
	else		update(t[i].r,mid+1,r,t[pre].r,x);
}
int query(int i,int l,int r,int pre,int k){
	if(l==r)	return l;
	if(t[t[i].l].num-t[t[pre].l].num>k)	return query(t[i].l,l,mid,t[pre].l,k);
	if(t[t[i].r].num-t[t[pre].r].num>k)	return query(t[i].r,mid+1,r,t[pre].r,k);
	return 0;
}
int main(){
	n=read();	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		update(rt[i],1,n,rt[i-1],a[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;	x=read();	y=read();
		printf("%d\n",query(rt[y],1,n,rt[x-1],(y-x+1)/2));
	}
}
/*
Input
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Output
1
0
3
0
4
*/
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

题目二：hdu5919 Sequence II（模板题的简单变式）

题意：

给你n(n≤2∗10 ^ 5)个数，每个数的大小0<Ai≤2∗10 ^ 5。再给你m(m≤2∗10 ^ 5)个询问。对于每个询问输入l,r,表示Al…Ar这个区间我们得到每个数第一次出现的位置下标的排列，假设这个区间有k个不同的数，我们得到的排列是p1<p2<p3<…<pk，叫你求第(k+1)/2这个数是多少？

题解：

主席树模板题的变式，很容易想到其实就是找该区间中有多少种数的变形。

入门：SPOJ - DQUERY 求区间数字种类数

回顾一下这题的主席树做法：
给你 n 个数，然后有 q 个询问，每个询问会给你[l,r]，输出[l,r]之间有多少种数字。

对于第i课主席树，区间以i为右端点，记录每个数字最后一次出现的位置，在那些位置+1.
更新时，如果这个元素之前出现过，就把之前记录的位置储存的信息 -1，然后在新的位置储存的信息 +1
查询[l,r]，找第r课主席树，查询区间[l,n]。

第i个询问区间依赖于第i-1个询问的答案，所以是强制在线的。

因为要找每个数在该区间中第一次出现的位置，所以有个技巧是倒着插入主席树，每插入一个值，将当前数位置的贡献值+1，将之前已经出现过的该数的位置上的贡献值-1即可

#define mid	(l+r>>1)
const int maxn=2e5+7;
int T,n,m,rt[maxn],a[maxn],tot,p[maxn],mp[maxn];
struct node{	int l,r,sum;	}t[maxn*50];
void update(int &i,int l,int r,int pre,int x,int v){
	i=++tot;	t[i]=t[pre];	t[i].sum+=v;
	if(l==r)	return;
	if(x<=mid)	update(t[i].l,l,mid,t[pre].l,x,v);
	else	update(t[i].r,mid+1,r,t[pre].r,x,v);
}
int query(int i,int l,int r,int x,int y){
	if(l>y||r<x)	return 0;
	if(x<=l&&r<=y)	return t[i].sum;
	return query(t[i].l,l,mid,x,y)+query(t[i].r,mid+1,r,x,y);
}
int cc(int i,int l,int r,int k){
	if(l==r)	return l;
	if(t[t[i].l].sum>=k)	return cc(t[i].l,l,mid,k);
	return cc(t[i].r,mid+1,r,k-t[t[i].l].sum);
}
void init(){
	tot=0;
	memset(rt,0,sizeof(rt));
	memset(mp,0,sizeof(mp));
}
int main(){
	T=read();
	for(int v=1;v<=T;v++){
		n=read();	m=read();
		init();
		for(int i=1;i<=n;i++)	a[i]=read();
		for(int i=n;i;i--){
			update(rt[i],1,n,rt[i+1],i,1);
			if(mp[a[i]])	update(rt[i],1,n,rt[i],mp[a[i]],-1);
			mp[a[i]]=i;
		}
		int temp=0;
		for(int i=1;i<=m;i++){
			int x,y;	x=read();	y=read();
			x=(x+temp)%n+1;	y=(y+temp)%n+1;
			if(x>y)	swap(x,y);
			int ans=query(rt[x],1,n,x,y);
			ans=(ans+1)/2;
			p[i]=temp=cc(rt[x],1,n,ans);
		}
		printf("Case #%d:",v);
		for(int i=1;i<=m;i++)	printf(" %d",p[i]);
		putchar('\n');
	}
	
}
/*
Input
2
5 2
3 3 1 5 4
2 2
4 4
5 2
2 5 2 1 2
2 3
2 4
Output
Case #1: 3 3
Case #2: 3 1
*/
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
66