相信很多人在学习莫队，刷莫队题目时，回不可避免的遇到一个数据结构 —— 值域分块。这篇文章就是帮助各位快速入门的。

Q1

给定一个序列，实现单点修改以及区间查询，保证修改次数不超过 \(10^7\) 次，查询次数不超过 \(10^5\) 次，序列长度不超过 \(10^5\) 。

A1

首先要求的是 \(O(1)\) 修改，\(O(\sqrt n)\) 查询。

那么考虑分块。

令 \(block[i]\) 表示 \(\sum_{j=(i-1)\times B}^{i \times B} a_j\)

显然对于点 \(x\) 的修改只需要对相应的 \(block\) 数组进行修改就可以维护 \(block\) 数组。

如果要统计区间之和时利用 \(block\) 数组就可以达到 \(O(B + n/B)\) 。

令 \(B = \sqrt n\) ，则达到 \(O(1)\) 修改，\(O(\sqrt n)\) 查询的数据结构。

Q2 （可持久化线段树 2）

给定一个序列，求区间排名为 \(k\) 的数。

A2

我们用莫队维护。

这个时候我们需要维护一个集合中的加数减数以及查询排名。

用线段树或者平衡树复杂度是 \(O(q \sqrt n \log n)\) 的，怎么办？

我们注意到，这个集合有 $ n\sqrt n$ 次加数减数，但只有 \(n\) 次查询操作。

那我们考虑值域分块。

令 \(a[i]\) 表示数 \(i\) 的出现次数。并记录 \(block\) 数组。

注意道倘若查询第 \(k\) 名，我们可以依次遍历 \(block\) 数组，倘若确定在某一个数组所包含的范围内，就暴力去查询。

显然，若每个 \(block\) 数组范围大小为 \(\sqrt n\) ，这个操作复杂度是 \(\sqrt n\) 的（已经离散化）。

参考代码：

#include<bits/stdc++.h>
#define warma 316
//#define int long long
//#define lowbit(x) (x&-(x))
using namespace std;
const int maxn = 2e5+10;
int n,m;
struct query{
	int l,r,k,id;
}q[maxn];
int sq;
bool cmp(query a,query b){
	if(a.l/sq==b.l/sq){
		return a.r>b.r;
	}
	else{
		return a.l<b.l;
	}
}
int anser[maxn];
int sum[maxn];
int cnt[maxn];
int a[maxn],b[maxn];
map<int,int> f;
void add(int x,int val){
	int bl=x/warma;
	cnt[x]+=val;
	sum[bl]+=val;
}
int rk(int k){
	for(int i=0;i<=warma;i++){
		if(k<=sum[i]){
			for(int j=i*warma;j<=(i+1)*warma;j++){
				if(k<=cnt[j]){
					return j;
				}
				else{
					k-=cnt[j];
				}
			}			
		}
		else{
			k-=sum[i];
		}
	}
}
int ls(int x){
	int l=0,r=n+1;
	while(l+1<r){
		int mid=(l+r)/2;
		if(x<=b[mid]){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	f[l]=x;
	return l;
} 

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
sq=sqrt(n);
for(int i=1;i<=n;i++){
	cin>>a[i];
	b[i]=a[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
	a[i]=ls(a[i]);
}
for(int i=1;i<=m;i++){
	cin>>q[i].l>>q[i].r>>q[i].k;
	q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int L=1,R=1;
add(a[1],1);
for(int i=1;i<=m;i++){
	while(L>q[i].l){
		L--;
		add(a[L],1);
	}
	while(R<q[i].r){
		R++;
		add(a[R],1);
	}
	while(L<q[i].l){
		add(a[L],-1);
		L++;
	}
	while(R>q[i].r){
		add(a[R],-1);
		R--;
	}
	anser[q[i].id]=f[rk(q[i].k)];
}
for(int i=1;i<=m;i++) cout<<anser[i]<<'\n';
return 0;
}

Q3 （Rmq Problem / mex）

有一个长度为 \(n\) 的数组 \(\{a_1,a_2...a_n\}\) ，\(m\) 次询问，每次询问一个区间内最小没有出现过的自然数。

A3

依旧考虑值域分块，这次我们用 \(block\) 数组记录对应范围内出现次数为 \(0\) 的数字数数量并用 \(cnt\) 数组记录每个数字的出现次数。

那么便利出第一个 \(block[i]\) 不等于 \(0\) 的范围，在暴力在这个范围内查找即可。

复杂度 \(O(n \sqrt n)\) 需要 o2 或者卡常。

参考代码：

#include<bits/stdc++.h>
using namespace std; 
const int maxn= 2e5+100;
int n,m;
struct q{
	int id;
	int l;
	int r;
	int anser;
}y[maxn]; 
int block[1000];
int sq;
int cnt[maxn];
void Add(int x){
	
	int bl=x/sq+1;
	if(x%sq==0){
		bl--;
	}
	if(cnt[x]==0){
		block[bl]--;
	}
	cnt[x]++;
	if(cnt[x]==0){
		block[bl]++;
	}
}
void Del(int x){
	int bl=x/sq+1;
	if(x%sq==0){
		bl--;
	}
	if(cnt[x]==0){
		block[bl]--;
	}
	cnt[x]--;
	if(cnt[x]==0){
		block[bl]++;
	}
}
int query(){
	for(int i=1;i<=500;i++){
		if(block[i]>0){
			for(int j=(i-1)*sq+1;j<=i*sq;j++){
				if(cnt[j]==0){
					return j;
				}
			}
		}
	}
}
int a[maxn];
bool cmp(q a, q b)
{
    return (a.l/sq)==(b.l/sq) ? a.r<b.r : a.l<b.l;
}
bool cmp1(q a,q b)
{
	return a.id<b.id;
}
int main()
{
	cin>>n>>m;
	sq=sqrt(n);
	for(int i=1;i<=500;i++){
		block[i]=sq;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]>n) a[i]=n+1;
		a[i]++;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>y[i].l>>y[i].r;
		y[i].id=i;
	}
	sort(y+1,y+m+1,cmp);
	int L=1;
	int R=1;
	Add(a[1]); 
	for(int i=1;i<=m;i++)
	{
		while(L>y[i].l)
		{
			L--;
			Add(a[L]);
		}
		while(R<y[i].r)
		{
			R++;
			Add(a[R]);
		}
		while(L<y[i].l)
		{
			Del(a[L]);
			L++;
		}
		while(R>y[i].r)
		{
		Del(a[R]);
		R--;
		}
	 	y[i].anser=query();
	}
	sort(y+1,y+m+1,cmp1);
	for(int i=1;i<=m;i++)
	cout<<y[i].anser-1<<endl;
}

Q4 （ AHOI2013 作业）

题面传送门

A4

几乎可以称得上是板子题。

用两个数组分别维护每个数是否出现以及出现次数，然后再分别用值域分块维护即可。

注意莫队的块长为 \(n / \sqrt m\) ，值域分块块长为 \(\sqrt V\) （\(V\) 表示值域）。

参考代码：

#include<bits/stdc++.h>
using namespace std; 
const int maxn= 3e5+100;
int n,m;
struct q{
	int id;
	int l;
	int r;
	int a;
	int b;
	int anser1;
	int anser2;
}y[maxn]; 
int block[1000][2];
int sq;
int B=500;
int cnt[maxn][2];
void Add(int x){
	int bl=x/B+1;
	if(x%B==0){
		bl--;
	}
	if(cnt[x][0]==0)
		cnt[x][1]++,block[bl][1]++;	
	cnt[x][0]++,block[bl][0]++;	
}
void Del(int x){
	int bl=x/B+1;
	if(x%B==0){
		bl--;
	}
	if(cnt[x][0]==1){
		cnt[x][1]--,block[bl][1]--;
	}
	cnt[x][0]--,block[bl][0]--;
}
int ask(int a,int b,int type){
	int bl=a/B+1;
	if(a%B==0){
		bl--;
	}
	int br=b/B+1;
	if(b%B==0){
		br--;
	}
	if(bl==br){
		int res=0;
		for(int i=a;i<=b;i++){
			res+=cnt[i][type];
		}
		return res;
	}
	int res=0;
	for(int i=bl+1;i<br;i++){
		res+=block[i][type];
	}
	for(int i=a;i<=bl*B;i++) res+=cnt[i][type];
	for(int i=(br-1)*B+1;i<=b;i++) res+=cnt[i][type];
	return res;
}
int a[maxn];
bool cmp(q a, q b)
{
    return (a.l/sq)==(b.l/sq) ? a.r<b.r : a.l<b.l;
}
bool cmp1(q a,q b)
{
	return a.id<b.id;
}
int main()
{
	cin>>n>>m;
	sq=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>y[i].l>>y[i].r>>y[i].a>>y[i].b;
		y[i].id=i;
	}
	sort(y+1,y+m+1,cmp);
	int L=1;
	int R=1;
	Add(a[1]); 
	for(int i=1;i<=m;i++)
	{
		while(L<y[i].l)
		{
			Del(a[L]);
			L++;
		}
		while(L>y[i].l)
		{
			L--;
			Add(a[L]);
		}
		while(R<y[i].r)
		{
			R++;
			Add(a[R]);
		}
		while(R>y[i].r)
		{
		Del(a[R]);
		R--;
		}
	 	y[i].anser1=ask(y[i].a,y[i].b,0);
	 	y[i].anser2=ask(y[i].a,y[i].b,1);
	}
	sort(y+1,y+m+1,cmp1);
	for(int i=1;i<=m;i++)
	cout<<y[i].anser1<<' '<<y[i].anser2<<endl;
}