Reku
0%

可持久化线段树

Posted on Edited on In Views: Valine:

学习了一发早就应该会的可持久化线段树。 可持久化的概念就是可以访问这个数据结构每一个时间点的信息。 线段树的可持久化就是每个修改都单独新建\(logN\)个节点，这样可以在时间复杂度不变，空间复杂度多乘一个\(logN\)的代价下，维护所有的信息。 BZOJ 3524

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

把每个位置的值插进线段树，然后用线段树来维护一个区间的和。询问就是用后面的线段树减去前面的线段树就好了。

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
#include<bits/stdc++.h>
#define maxn 500010
using namespace std;
int n,m,x,tt;
int root[maxn],ls[maxn*20],rs[maxn*20],sum[maxn*20];
void update(int l,int r,int x,int &y,int p)
{
	y=++tt;
	sum[y]=sum[x]+1;
	ls[y]=ls[x]; rs[y]=rs[x];
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) update(l,mid,ls[x],ls[y],p);
	else update(mid+1,r,rs[x],rs[y],p);
}
int query(int l,int r)
{
	int tmp=(r-l+1)>>1;
	int a=1,b=n;
	int mid,x,y;
	x=root[l-1]; y=root[r];
	while(a<b)
	{
		if(sum[y]-sum[x]<=tmp) return 0;
		mid=(a+b)>>1;
		if(sum[ls[y]]-sum[ls[x]]>tmp)
		{
			b=mid; x=ls[x]; y=ls[y];
		}
		else if(sum[rs[y]]-sum[rs[x]]>tmp)
		{
			a=mid+1; x=rs[x]; y=rs[y];
		}
		else return 0;
	}
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		update(1,n,root[i-1],root[i],x);
	}
	int a,b;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",query(a,b));
	}
	return 0;
}

http://codeforces.com/contest/538/problem/F 根据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
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define maxn 200010
#define pb push_back
using namespace std;
int n;
int a[maxn];
vector<int> w;
unordered_map<int,int> ha;
int sz;
int tt;
int root[maxn],ls[maxn*20],rs[maxn*20],sum[maxn*20];
void update(int l,int r,int x,int &y,int p)
{
	y=++tt;
	sum[y]=sum[x]+1;
	ls[y]=ls[x]; rs[y]=rs[x];
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) update(l,mid,ls[x],ls[y],p);
	else update(mid+1,r,rs[x],rs[y],p);
}
int query(int l,int r,int v)
{
	if(l>n) return 0;
	l=min(n,l); r=min(n,r);
	int a=1,b=sz;
	int mid,x,y;
	x=root[l-1]; y=root[r];
	int ans=0;
	while(a<b)
	{
		mid=(a+b)>>1;
		if(v<=mid)
		{
			b=mid; x=ls[x]; y=ls[y];
		}
		else
		{
			ans+=sum[ls[y]]-sum[ls[x]];
			a=mid+1; x=rs[x]; y=rs[y];
		}
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		w.pb(a[i]);
	}
	sort(w.begin(),w.end());
	for(int i=0;i<w.size();i++)
	{
		if(i==0||w[i]!=w[i-1]) ha[w[i]]=++sz;
	}
	int ans;
	for(int i=1;i<=n;i++) a[i]=ha[a[i]];
	for(int i=1;i<=n;i++) update(1,sz,root[i-1],root[i],a[i]);
	for(int k=1;k<=n-1;k++)
	{
		ans=0;
		for(int i=1,j=0;j<=n;i++)
		{
			ans+=query(k*(i-1)+2,k*i+1,a[i]);
			j=k*i+1;
		}
		printf("%d ",ans);
	}
	return 0;
}