直接进入正题:


分块:

分块分块,就是把一个长串东西,分为许多块,这样,我们就可以在操作一个区间的时候,对于在区间里面完整的块,直接操作块,不完整的直接操作即可,因为不完整,再加上一个块本身就不大,复杂度会很小的,然后需要输出的时候,单点输出直接把本来自身的值加上对块的操作加起来即可,而对于区间询问,格外在维护一个区间总和数组即可。那么问题来了:分为几块呢? 答案是当大小为\(n\)的序列,分为\(\sqrt{n}\),因为对于上述的操作,设块数为\(k\),复杂度是为\(O(\frac{n}{k}+k)\)的,根据计算,可以得出\(k\)为\(\sqrt{n}\)时复杂度最优。

下面给出例题来讲解吧\(qwq\)。


例题:开关

这道题就是一个区间修改+区间查询的裸题了,他操作一次,就相当于加一次,看最后mod2为几,1则是开着的,0则是关着的。然后还有一个点,对于区间操作时,我们维护一个\(ans_i\)代表第\(i\)块块的总开灯数,如果这一个块都被操作了,就可以\(ans_i=sq-ans_i\),\(sq\)为块的大小,是一个定值,就是\(\sqrt{n}\)(因为分为了\(\sqrt{n}\)块嘛,一块大小当然也为\(\sqrt{n}\)咯)。

\(code\)时间:

#include <bits/stdc++.h>
using namespace std;
int n , m , sq;
int a[100010] , f[100010] , tag[10010] , ans[10010]; //a存放灯泡是否开着的,f为当前的位置为第几块,tag是区间标记,ans就是区间和
void work(int x , int y){
for(int i = x; i <= min(y , f[x] * sq)/*有可能不构成一块,所以取min*/; i++){
if((a[i] + tag[f[i]]/*!!!这里一定要加上标记,调了好久*/) % 2) ans[f[i]]--; //为开着的关上后就是-1
else ans[f[i]]++;
a[i]++;
}
if(f[x] != f[y]) //在一块就说明区间不构成一块
for(int i = (f[y] - 1) * sq + 1; i <= y; i++){
if((a[i] + tag[f[i]]) % 2) ans[f[i]]--;
else ans[f[i]]++;
a[i]++;
}
for(int i = f[x] + 1; i <= f[y] - 1; i++){ //两边的前面已经处理过了
ans[i] = sq - ans[i];
tag[i]++;
}
}
int sum(int x , int y){
int k = 0;
for(int i = x; i <= min(y , f[x] * sq); i++) if((a[i] + tag[f[i]]) % 2) k++;
if(f[x] != f[y]) for(int i = (f[y] - 1) * sq + 1; i <= y; i++) if((a[i] + tag[f[i]]) % 2) k++;
for(int i = f[x] + 1; i <= f[y] - 1; i++) k += ans[i];
return k;
}
int main(){
cin >> n >> m;
sq = sqrt(n);
for(int i = 1; i <= n; i++) f[i] = (i - 1) / sq + 1; //标记某一个点是哪一块的
while(m--){
int x , y;
cin >> x;
if(!x){
cin >> x >> y;
work(x , y);
}else{
cin >> x >> y;
cout << sum(x , y) << endl;
}
}
return 0;
}

我讲的很差对吧,这应该只是作为我的应该记录吧,如果真的要学习分块,去看hzwer大佬的分块九讲吧,非常清晰。

05-11 14:02
查看更多