分块算法总结

又是一种神奇的暴力。

分块，顾名思义，就是把序列分成块来做。

分成块，每个块暴力，就是它的基本思路。

它能解决一类无脑更新，无脑修改区间问题。

我们先看一道例题

luogu3374

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

14
16

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

这题的名字叫树状数组模版，当然是可以用树状数组做了。但是假如我不想写树状数组的话，也是可以用分块水过去的。

下面就真正讲一下分块的过程：

0.初始化

我们首先把求出块的大小

\(block = \sqrt n \)

然后求出一共有多少个块

\(num = n \div block \)

再求出每一个块的左右端点

\(l[i] = (i-1) \times block + 1\)

\(r[i] = i \times block\)

最后求一下每个节点属于哪个块

\( belong[i] = (i-1) \div block + 1\)

然后就初始化完了（有可能还要维护一下别的值）

这个步骤一般所有分块都有。

对于这道题，还有以下的步骤。。

1.区间和

我们会得到一个区间[L,R]

假如LR在一个块内，直接暴力！

if (belong[L]==belong[R])
{
	for (int i=L;i<=R;i++)
		ans+=a[i];
	printf("%d\n",ans);
	return;
}

假如不在一个块内，会分成两种区间

一种是橘色的，一种是红色的。

橘色的直接暴力！

for (int i=L;i<=r[belong[L]];i++)
	ans+=a[i];

for (int i=l[belong[R]];i<=R;i++)
	ans+=a[i];

红色的统计一下块值就可以了

for (int i=belong[L]+1;i<belong[R];i++)
	ans+=d[i];

然后就出来了，是不是很简单

2.单点改

直接改一下，更新块就可以了

d[belong[pos]]+=x;
a[pos]+=x;

总程序

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int n,m,num,q,x,com,y,z,belong[maxn],block,l[maxn],r[maxn],a[maxn],mark[maxn];
int d[maxn];
char s[10];
//num分块的个数
//belong[i]表示i属于哪一块
//block表示块的大小
//l[i]表示i这块的左端点位置
//r[i]表示右端点位置
void debug()
{
	for (int i=1;i<=n;i++)
		printf("%d ",a[i]);
	puts("");
}
void build()
{
	block=sqrt(n);
	num=n/block;if (n%block) num++;
	for (int i=1;i<=num;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	for (int i=1;i<=n;i++)
		belong[i]=(i-1)/block+1;
	for (int i=1;i<=n;i++)
		d[belong[i]]+=a[i];
}
void update(int pos,int x)
{
	d[belong[pos]]+=x;
	a[pos]+=x;
}
void query(int L,int R)
{
	int ans=0;
	if (belong[L]==belong[R])
	{
		for (int i=L;i<=R;i++)
			ans+=a[i];
		printf("%d\n",ans);
		return;
	}

	for (int i=L;i<=r[belong[L]];i++)
		ans+=a[i];

	for (int i=l[belong[R]];i<=R;i++)
		ans+=a[i];

	for (int i=belong[L]+1;i<belong[R];i++)
		ans+=d[i];
	printf("%d\n",ans);
}
main()
{
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build();
	for (int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&com,&x,&y);
		if (com==2)
			query(x,y);
		else
			update(x,y);
	}
}

下一道题

luogu3368

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x 含义：输出第x个数的值

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

6
10

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

这个题和上面的差不多

初始化差不多

两个操作

1.单点查询

直接输出，O(1)

2.区间加

对于每个块，加上一个mark，假如要用这个块的话，先把mark加上，再操作。

注意细节

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int n,m,num,q,x,com,y,z,belong[maxn],block,l[maxn],r[maxn],a[maxn],mark[maxn];
char s[10];
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void debug()
{
    for (int i=1;i<=n;i++)
        printf("%d ",a[i]);
    puts("");
}
void build()
{
    block=sqrt(n);
    num=n/block;if (n%block) num++;
    for (int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    for (int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
}
void update(int L,int R,int x)
{
    int ans=0;
    if (belong[L]==belong[R])
    {
        for (int i=l[belong[L]];i<=r[belong[R]];i++)
            a[i]+=mark[belong[L]];
        mark[belong[L]]=0;
        for (int i=L;i<=R;i++)
            a[i]+=x;
        return;
    }

    for (int i=l[belong[L]];i<=r[belong[L]];i++)
        a[i]+=mark[belong[L]];
    mark[belong[L]]=0;
    for (int i=L;i<=r[belong[L]];i++)
        a[i]+=x;

    for (int i=l[belong[R]];i<=r[belong[R]];i++)
        a[i]+=mark[belong[R]];
    mark[belong[R]]=0;
    for (int i=l[belong[R]];i<=R;i++)
        a[i]+=x;

    for (int i=belong[L]+1;i<belong[R];i++)
        mark[i]+=x;
}
main()
{
    n=read(),q=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    build();
    for (int i=1;i<=q;i++)
    {
        com=read(),x=read();
        if (com==2)
            printf("%d\n",a[x]+mark[belong[x]]);
        else
            y=read(),z=read(),update(x,y,z);
    }
}

第三道例题

luogu3372

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

11
8
20

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

其实就是前两个题结合一下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
int n,m,num,q,belong[maxn],block,l[maxn],r[maxn];
LL a[maxn],mark[maxn],d[maxn],x,com,y,z;
char s[10];
LL inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void debug()
{
	for (int i=1;i<=n;i++)
		printf("%lld ",a[i]+mark[belong[i]]);
	puts("");
	for (int i=1;i<=num;i++,puts(""))
		printf("Bolck%lld: l:%lld r:%lld sum:%lld",i,l[i],r[i],d[i]+mark[i]*block);
}
void build()
{
	block=sqrt(n);
	num=n/block;if (n%block) num++;
	for (int i=1;i<=num;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	for (int i=1;i<=n;i++)
		belong[i]=(i-1)/block+1;
	for (int i=1;i<=n;i++)
		d[belong[i]]+=a[i];
}
void update(int L,int R,LL x)
{
	if (belong[L]==belong[R])
	{
		for (int i=l[belong[L]];i<=r[belong[R]];i++)
			a[i]+=mark[belong[L]];
		d[belong[L]]+=mark[belong[L]]*block;
		mark[belong[L]]=0;
		for (int i=L;i<=R;i++)
			a[i]+=x;
		d[belong[L]]+=(R-L+1)*x;
		return;
	}

	for (int i=l[belong[L]];i<=r[belong[L]];i++)
		a[i]+=mark[belong[L]];
	d[belong[L]]+=mark[belong[L]]*block;
	mark[belong[L]]=0;
	for (int i=L;i<=r[belong[L]];i++)
		a[i]+=x;
	d[belong[L]]+=(r[belong[L]]-L+1)*x;

	for (int i=l[belong[R]];i<=r[belong[R]];i++)
		a[i]+=mark[belong[R]];
	d[belong[R]]+=mark[belong[R]]*block;
	mark[belong[R]]=0;
	for (int i=l[belong[R]];i<=R;i++)
		a[i]+=x;
	d[belong[R]]+=(R-l[belong[R]]+1)*x;

	for (int i=belong[L]+1;i<belong[R];i++)
		mark[i]+=x;
}
void query(int L,int R)
{
	LL ans=0;
	if (belong[L]==belong[R])
	{
		for (int i=L;i<=R;i++)
			ans+=a[i];
		printf("%lld\n",ans+(R-L+1)*mark[belong[R]]);
		return;
	}

	for (int i=L;i<=r[belong[L]];i++)
		ans+=a[i]+mark[belong[L]];

	for (int i=l[belong[R]];i<=R;i++)
		ans+=a[i]+mark[belong[R]];

	for (int i=belong[L]+1;i<belong[R];i++)
		ans+=d[i]+mark[i]*block;
	printf("%lld\n",ans);
}
main()
{
	n=read(),q=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	build();
	for (int i=1;i<=q;i++)
	{
		com=read(),x=read(),y=read();
		if (com==2)
			query(x,y);
		else
			z=read(),update(x,y,z);
	}
}

还有一道

luogu3373

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.将某区间每一个数乘上x

3.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k

操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k

操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果

输出格式：

输出包含若干行整数，即为所有操作3的结果。

输入输出样例

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

17
2

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

这题就比较蛋疼了，但是可以想一下线段树的mark，还是能写一写的

可惜被卡常了，无限70

【复杂度明明是过的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000;
int n,m,num,mod,q,belong[maxn],block,l[maxn],r[maxn];
LL a[maxn],add[maxn],mul[maxn],d[maxn],x,com,y,z;
char s[10];
LL inline read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void build()
{
	block=sqrt(n);
	num=n/block;if (n%block) num++;
	for (int i=1;i<=num;i++)
		l[i]=(i-1)*block+1,r[i]=i*block,mul[i]=1;
	for (int i=1;i<=n;i++)
		belong[i]=(i-1)/block+1;
	for (int i=1;i<=n;i++)
		d[belong[i]]+=a[i];
}
void update_add(int L,int R,LL x)
{
	int bl=belong[L],br=belong[R];
	if (bl==br)
	{
		if (add[bl]||mul[bl]!=1)
		{
			for (int i=l[bl];i<=r[bl];i++)
				a[i]=(a[i]*mul[bl]+add[bl])%mod;
			d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
			add[bl]=0,mul[bl]=1;
		}
		for (int i=L;i<=R;i++)
			a[i]+=x;
		d[bl]=(d[bl]+(R-L+1)*x)%mod;
		return;
	}

	if (add[bl]||mul[bl]!=1)
	{
		for (int i=l[bl];i<=r[bl];i++)
			a[i]=(a[i]*mul[bl]+add[bl])%mod;
		d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
		add[bl]=0,mul[bl]=1;
	}
	for (int i=L;i<=r[bl];i++)
		a[i]=(a[i]+x)%mod;
	d[bl]=(d[bl]+(r[bl]-L+1)*x)%mod;

	if (add[br]||mul[br]!=1)
	{
		for (int i=l[br];i<=r[br];i++)
			a[i]=(a[i]*mul[br]+add[br])%mod;
		d[br]=(d[br]*mul[br]+add[br]*block)%mod;
		add[br]=0,mul[br]=1;
	}
	for (int i=l[br];i<=R;i++)
		a[i]=(a[i]+x)%mod;
	d[br]=(d[br]+(R-l[br]+1)*x)%mod;

	for (int i=bl+1;i<br;i++)
		add[i]=(add[i]+x)%mod;
}
void update_mul(int L,int R,LL x)
{
	int bl=belong[L],br=belong[R];
	if (bl==br)
	{
		if (add[bl]||mul[bl]!=1)
		{
			for (int i=l[bl];i<=r[bl];i++)
				a[i]=(a[i]*mul[bl]+add[bl])%mod;
			d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
			add[bl]=0,mul[bl]=1;
		}
		int more=0;
		for (int i=L;i<=R;i++)
			more=(more+a[i]*(x-1))%mod,a[i]=(a[i]*x)%mod;
		d[bl]=(d[bl]+more)%mod;
		return;
	}

	if (add[bl]||mul[bl]!=1)
	{
		for (int i=l[bl];i<=r[bl];i++)
			a[i]=(a[i]*mul[bl]+add[bl])%mod;
		d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
		add[bl]=0,mul[bl]=1;
	}
	int more=0;
	for (int i=L;i<=r[bl];i++)
		more=(more+a[i]*(x-1))%mod,a[i]=(a[i]*x)%mod;
	d[bl]=(d[bl]+more)%mod;

	if (add[br]||mul[br]!=1)
	{
		for (int i=l[br];i<=r[br];i++)

			a[i]=(a[i]*mul[br]+add[br])%mod;
		d[br]=(d[br]*mul[br]+add[br]*block)%mod;
		add[br]=0,mul[br]=1;
	}
	more=0;
	for (int i=l[br];i<=R;i++)
		more=(more+a[i]*(x-1))%mod,a[i]=(a[i]*x)%mod;
	d[br]=(d[br]+more)%mod;

	for (int i=bl+1;i<br;i++)
		mul[i]=(mul[i]*x)%mod,
		add[i]=(add[i]*x)%mod;
}
void query(int L,int R)
{
	LL ans=0;
	int bl=belong[L],br=belong[R];
	if (bl==br)
	{
		for (int i=L;i<=R;i++)
			ans=(ans+a[i])%mod;
		printf("%lld\n",(ans*mul[bl]+(R-L+1)*add[bl])%mod);
		return;
	}

	for (int i=L;i<=r[bl];i++)
		ans=(ans+a[i])%mod;
	ans=(ans*mul[bl]+(r[bl]-L+1)*add[bl])%mod;

	int temp=0;
	for (int i=l[br];i<=R;i++)
		temp=(temp+a[i])%mod;
	temp=(temp*mul[br]+(R-l[br]+1)*add[br])%mod;
	ans=(ans+temp)%mod;

	for (int i=bl+1;i<br;i++)
		ans=(ans+d[i]*mul[i]+add[i]*block)%mod;
	printf("%lld\n",ans);
}
int main()
{
	n=read(),q=read(),mod=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	build();
	for (int i=1;i<=q;i++)
	{
		com=read(),x=read(),y=read();
		if (com==3)
			query(x,y);
		else
		if (com==1)
			z=read(),update_mul(x,y,z);
		else
			z=read(),update_add(x,y,z);
	}
}

附一个生成器

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <sstream>
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;

stringstream ss;

int main(int a1,char *a2[])
{
	int seed=time(0);
	if (a1)
	{
		ss.clear();
		ss<<a2[1];
		ss>>seed;
	}
	srand(seed);

	int n=random(1,100000),m=random(1,100000);
	printf("%d %d 100000007\n",n,m);
	for (int i=1;i<=n;i++)
		printf("%d ",random(1,1000));
	puts("");
	for (int i=1;i<=m;i++)
	{
		int com=random(1,3);
		printf("%d ",com);
		if (com==1 || com==2)
		{
			int x=random(1,n),y=random(1,n);
			if (x>y) swap(x,y);
			printf("%d %d %d\n",x,y,random(1,1000));
		}
		if (com==3)
		{
			int x=random(1,n),y=random(1,n);
			if (x>y) swap(x,y);
			printf("%d %d\n",x,y);
		}
	}
}

下面讲一道真正的分块题。

luogu2801

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。

每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）

CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。

WD巨懒，于是他把这个回答的任务交给了你。

输入输出格式

输入格式：

第1行为两个整数N、Q。Q为问题数与教主的施法数总和。

第2行有N个正整数，第i个数代表第i个英雄的身高。

第3到第Q+2行每行有一个操作：

（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。

（2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

输出格式：

对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。

输入输出样例

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

2
3

说明

【输入输出样例说明】

原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。

【数据范围】

对30%的数据，N≤1000，Q≤1000。

对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。

这题一眼是主席树啊，但是数据范围太zz了【好像主席树随便什么数据都能卡了

于是，我们开始暴力分块

该怎么维护这个分块呢

时刻不要忘了，分块就是暴力。

使每个块内有序，查找时二分，好像不错。

怎么保持有序？

每个块暴力sort！

更新如何保持有序

暴力sort！

明确这几点就可以肝了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000006;
int n,m,num,q,x,y,z,belong[maxn],block,l[maxn],r[maxn],a[maxn],mark[maxn];
int d[maxn];
char s[10];
void build()
{
	block=sqrt(n);
	num=n/block;if (n%block) num++;
	for (int i=1;i<=num;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	for (int i=1;i<=n;i++)
		belong[i]=(i-1)/block+1;
	for (int i=1;i<=n;i++)
		d[i]=a[i];
	for (int i=1;i<=num;i++)
		sort(d+l[i],d+r[i]+1);
}
void update(int L,int R,int x)
{
	if (belong[L]==belong[R])
	{
		for(int i=l[belong[L]];i<=r[belong[R]];i++)
            a[i]+=mark[belong[L]];
        mark[belong[L]]=0;
        for(int i=L;i<=R;i++)
            a[i]+=x;
        for(int i=l[belong[L]];i<=r[belong[R]];i++)
            d[i]=a[i];
        sort(d+l[belong[L]],d+r[belong[R]]+1);
		return;
	}
	for(int i=l[belong[L]];i<=r[belong[L]];i++)
        a[i]+=mark[belong[L]];
    mark[belong[L]]=0;
    for(int i=L;i<=r[belong[L]];i++)
        a[i]+=x;
    for(int i=l[belong[L]];i<=r[belong[L]];i++)
        d[i]=a[i];
    sort(d+l[belong[L]],d+r[belong[L]]+1);

    for(int i=l[belong[R]];i<=r[belong[R]];i++)
        a[i]+=mark[belong[R]];
    mark[belong[R]]=0;
    for(int i=l[belong[R]];i<=R;i++)
        a[i]+=x;
    for(int i=l[belong[R]];i<=r[belong[R]];i++)
        d[i]=a[i];
    sort(d+l[belong[R]],d+r[belong[R]]+1);
	for (int i=belong[L]+1;i<belong[R];i++)
		mark[i]+=x;
}
void query(int L,int R,int k)
{
	int ans=0;
	if (belong[L]==belong[R])
	{
		for (int i=L;i<=R;i++)
			if (a[i]+mark[belong[i]]>=k)
				ans++;
		printf("%d\n",ans);
		return;
	}

	for (int i=L;i<=r[belong[L]];i++)
		if (a[i]+mark[belong[i]]>=k)
			ans++;

	for (int i=l[belong[R]];i<=R;i++)
		if (a[i]+mark[belong[i]]>=k)
			ans++;

	for (int i=belong[L]+1;i<belong[R];i++)
	{
		int l1=l[i],r1=r[i],temp=0;
		while(l1<=r1)
		{
			int mid=(l1+r1)/2;
			if (d[mid]+mark[i]>=k)
				r1=mid-1,temp=r[i]-mid+1;
			else
				l1=mid+1;
		}
		ans+=temp;
	}
	printf("%d\n",ans);
}
main()
{
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build();
	for (int i=1;i<=q;i++)
	{
		scanf("%s%d%d%d",s,&x,&y,&z);
		if (s[0]=='A')
			query(x,y,z);
		else
			update(x,y,z);
	}
}

最后一道题

分块+莫队

bzoj3809

3809: Gty的二逼妹子序列

Time Limit: 80 Sec Memory Limit: 28 MB
Submit: 1648 Solved: 489

Description

Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。
Input

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。
第二行包括n个整数s1…sn(1<=si<=n)。
接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。
Output

对每个询问，单独输出一行，表示sl…sr中权值∈[a,b]的权值的种类数。

Sample Input

10 10

4 4 5 1 4 1 5 1 2 1

5 9 1 2

3 4 7 9

4 4 2 5

2 3 4 7

5 10 4 4

3 9 1 1

1 4 5 9

8 9 3 3

2 2 1 6

8 9 1 4

Sample Output

2

0

0

2

1

1

1

0

1

2

HINT

样例的部分解释：
5 9 1 2

子序列为4 1 5 1 2

在[1,2]里的权值有1,1,2，有2种，因此答案为2。
3 4 7 9

子序列为5 1

在[7,9]里的权值有5，有1种，因此答案为1。
4 4 2 5

子序列为1

没有权值在[2,5]中的，因此答案为0。
2 3 4 7

子序列为4 5

权值在[4,7]中的有4,5，因此答案为2。
建议使用输入/输出优化。

这题就非常的有趣了

需要对权值分块，对序列莫队

对序列莫队比较好理解，对权值就相当于分块就是维护一个桶，每次查询桶中[l,r]的元素数量。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n,m,num,x,com,y,z,belong[maxn],block,l[maxn],r[maxn],a[maxn];
int d[maxn],pos[maxn],c[maxn],anslist[1000010];
char s[10];
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct quest
{
	int l,r,a,b,id;
}q[1000010];
bool comp(quest a,quest b)
{
	if (pos[a.l]==pos[b.l])
		return a.r<b.r;
	return pos[a.l]<pos[b.l];
}
void build()
{
	block=sqrt(n/2);
	num=n/block;if (n%block) num++;
	for (int i=1;i<=num;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	r[num]=n;
	for (int i=1;i<=n;i++)
		belong[i]=(i-1)/block+1;
}
void updates(int x)
{
	c[x]++;
	if (c[x]==1) d[belong[x]]++;
}
void deletes(int x)
{
	c[x]--;
	if (c[x]==0) d[belong[x]]--;
}
int query(int L,int R)
{
	int ans=0;
	if (belong[L]==belong[R])
	{
		for (int i=L;i<=R;i++)
			if (c[i])ans++;
		return ans;
	}
	for (int i=L;i<=r[belong[L]];i++)
		if (c[i])ans++;
	for (int i=l[belong[R]];i<=R;i++)
		if (c[i])ans++;
	for (int i=belong[L]+1;i<belong[R];i++)
		ans+=d[i];
	return ans;
}
int main()
{
	n=read(),m=read();
	int size=ceil(sqrt(n*1.0));
	for (int i=1;i<=n;i++)
		a[i]=read(),pos[i]=(i-1)/size;
	for (int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
	sort(q+1,q+m+1,comp);
	int L=1,R=0;
	build();
	for (int i=1;i<=m;i++)
	{
		while(L<q[i].l)
			deletes(a[L]),L++;
		while(L>q[i].l)
			L--,updates(a[L]);
		while(R>q[i].r)
			deletes(a[R]),R--;
		while(R<q[i].r)
			R++,updates(a[R]);
		anslist[q[i].id]=query(q[i].a,q[i].b);
	}
	for (int i=1;i<=m;i++)
		printf("%d\n",anslist[i]);
}

祝AC