题解 P4939 【Agent2】
Suuon_Kanderu
2020-03-04 19:32:05
有树状数组的地方，就少不了线段树。有线段树的地方，就少不了分块。~~我自己编的~~
**分块是一种很容易理解数据结构，他可以维护很多的东西**~~当然我都不会~~，本题解旨在让只能得暴力分的同学AC本题！学会分块的思想以及方法，会比较详细。
- 分块的思想
所谓分块，顾名思义，就是把一组数据分为若干块，从而提高效率。
举个例子：来看一组数据1,5,6,4,5。
我们把他分成$\sqrt{n}$个块（不同的情况块的数量不同，就是这样
| 编号 | 数值 | 第几块 |
| ----------- | ----------- | ----------- |
| 1 | 1 | 1 |
| 2 | 5 | 1 |
| 3 | 6 | 2 |
| 4 | 4 | 2 |
| 5 | 5 | 3 |
如果我们要让编号一到五加1，可以这样做：
1. 把第一块（1）的值 暴力 加1
2. 把中间块（2）的每个块的标记+1
（如何打标记？只要再开一个数组，记录每一块的统一加的值即可，相信学过线段树的同学一定很熟悉）
3. 把最后一块（3）的数值 暴力 加1
然后就是这样
|编号 | 数值 | 第几块 |
| ----------- | ----------- | ----------- | ----------- |
| 1 | 2（1+1） |1 |
| 2 | 6 （5+1）| 1 |
| 3 | 6 | 2 | |
| 4 | 4 | 2 | |
| 5 | 6 （5+1）|3 |
|第几块 | 标记 |
| ----------- | ----------- |
| 1 | 0 |
| 2 | 1（0+1） |
| 3 | 0 |
区间查询同理，只是暴力加的时候要加上打的标记。
单点查询就是把标记和数值加起来就OK。
- 具体实现
实现时我们要考虑一些细节。
1. 如果要操作的两个端点在一个块内，直接暴力相加。
2. 如果左端点或右端点本来就在块的开头或末尾，就别加了。
还是很好理解的
- 代码实现（本题
```cpp
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
const int N=10000000+100;
struct fk{//分块大法
int num,rank;//数值，第几块
}a[N];
int tag[N];//标记
#define rank(x) a[x].rank
#define tag(x) tag[x]
#define num(i) a[i].num
int n,bs,zo;//共有几个数，块的大小 ,总共有几个块
int qsum(int l){
return a[l].num + tag(rank(l));//单点查询
}
void change2(int l,int r,int add){
for (int i=l; i<=min(rank(l)*bs,r); i++)num(i)+=add;//这个是前面的块，这里后面解释
if (rank(l)!=rank(r))
for (int i=(rank(r)-1)*bs+1; i<=r; i++)num(i)+=add;//这个是后面的块，这里后面解释
for (int i=rank(l)+1; i<=rank(r)-1; i++)
tag(i)+=add;//这个是整块处理
}
void pr(){
printf("\tid\tnum\trank\n");
for(int i=1;i<=n;i++)printf("\t%d:\t%d\t%d\n",i,num(i),rank(i));
printf("\n\tid\ttag\n");
for(int i=1;i<=zo;i++)printf("\t%d:\t%d\t\n",i,tag(i));
}
signed main(){
cin>>n;bs=sqrt(n);
if(n/bs*bs==n)zo=n/bs; else zo=n/bs+1
//会不会有不完整的块;
int k;cin>>k;
for(int i=1;i<=n;i++){
a[i].num = 0;
a[i].rank=(i-1)/bs+1;
}
int l,r;
while(k--){
int op; scanf("%d",&op);
if(op==0){
scanf("%d%d",&l,&r);
change2(l,r,1);
}
if(op==1) {
scanf("%d",&l);
printf("%d\n",qsum(l));
}
}
return 0;
}
```
（大佬自行跳过此区域）
解释一下处理前面的块和后面的块的代码
min(rank(l)*bs,r)
rank（l） $\times$ bs就是第 I 个块 乘上 块的大小，很容易明白，就是块的最后一个元素。
用前面的数列，比如
rank(1) $\times$ 2 = 1 $\times$2 = 2
果然是第一个块的最后一个元素。
min()里面有个 r 是考虑左端点和右端点可能在一个块里，如果是，那么就直接暴力全加完，后面的操作其实都没执行。
(rank(r)-1)*bs+1同理，就是块的第一个元素。
简单粗暴