分块
复杂度\(O(n \sqrt n)\)
主要目的是解决一些区间操作问题
把区间拆分成 \(\sqrt{n}\) 大小的块
每次碰到修改的操作,对于散块,直接暴力操作,对于整块,那么用一个 \(tag\) 进行标记即可
也就是说对于一个操作 \([l,r]\) 来说
我们需要进行操作主要分三步:
- 暴力操作头散块,即 \([l, k1*block-1]\),在操作的同时,处理 \([(k1-1) * block, k1 * block - 1]\) 这一整块的 \(tag\)
- 中间所有的整块,对 \(tag\) 进行标记
- 暴力操作尾散块,即 \([k2*block, r]\),在操作的同时,处理 \([k2 * block, (k2+1) * block - 1]\) 这一整块的 \(tag\)
对于查询操作来说
- 暴力查询头散块,即 \([l, k1*block-1]\),在操作的同时,处理 \([(k1-1) * block, k1 * block - 1]\) 这一整块的 \(tag\)
- 查询中间所有的整块,拿一个数组 \(sum\) 记录每一整块现在的信息
- 暴力查询尾散块,即 \([k2*block, r]\),在操作的同时,处理 \([k2 * block, (k2+1) * block - 1]\) 这一整块的 \(tag\)
P2357 守墓人
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
int n,m,block,op,l,r,id[maxn];
ll a[maxn],sum[1005],tag[1005],x,res=0;
void change(int l,int r,ll x){
//1.左散块
for(int i=l;i<=min(id[l]*block,r);i++)
a[i]+=x,sum[id[i]]+=x;
if(id[l]==id[r]) return ;
//2.中间的整块
for(int i=id[l]+1;i<id[r];i++)
sum[i]+=1ll*x*block,tag[i]+=x;
//3.右散块
for(int i=(id[r]-1)*block+1;i<=r;i++)
a[i]+=x,sum[id[i]]+=x;
}
ll query(int l,int r){
res=0;
//1.左散块
for(int i=l;i<=min(id[l]*block,r);i++)
res+=a[i]+tag[id[i]];
if(id[l]==id[r]) return res;
//2.中间的整块
for(int i=id[l]+1;i<id[r];i++) res+=sum[i];
//3.右散块
for(int i=(id[r]-1)*block+1;i<=r;i++)
res+=a[i]+tag[id[i]];
return res;
}
int main(){
/*2023.4.8 hewanying P2357 守墓人 分块*/
scanf("%d%d",&n,&m);
block=(int)floor(sqrt(n));
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
id[i]=(i-1)/block+1;
sum[id[i]]+=a[i];
}
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d%lld",&l,&r,&x);
change(l,r,x);
}
else if(op==2){
scanf("%lld",&x);
change(1,1,x);
}
else if(op==3){
scanf("%lld",&x);
change(1,1,-x);
}
else if(op==4){
scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r));
}
else if(op==5){
printf("%lld\n",query(1,1));
}
}
return 0;
}
P.S:写代码的过程中要注意左右散块的两端值
P3870 [TJOI2009] 开关
题目描述
\(tag[i]\) 用于记录 \(i\) 这整块被异或的次数
\(sum[i]\) 用于记录 \(i\) 这整块开着灯的数量
整块操作:
tag[i] ^=1, sum[i] = block - sum[i];
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,block,op,l,r;
int sum[1005],tag[1005],a[maxn],id[maxn];
void change(int l,int r){
//1.左散块
for(int i=l;i<=min(r,id[l]*block);i++)
a[i]^=1,sum[id[i]]+=(a[i]^tag[id[i]])?1:-1;
if(id[l]==id[r]) return;
//2.中间的整块
for(int i=id[l]+1;i<id[r];i++)
tag[i]^=1,sum[i]=block-sum[i];
//3.右散块
for(int i=(id[r]-1)*block+1;i<=r;i++)
a[i]^=1,sum[id[i]]+=(a[i]^tag[id[i]])?1:-1;
}
int query(int l,int r){
int res=0;
//1.左散块
for(int i=l;i<=min(r,id[l]*block);i++)
res+=(a[i]^tag[id[i]]);
if(id[l]==id[r]) return res;
//2.中间的整块
for(int i=id[l]+1;i<id[r];i++)
res+=sum[i];
//3.右散块
for(int i=(id[r]-1)*block+1;i<=r;i++)
res+=(a[i]^tag[id[i]]);
return res;
}
int main(){
/*2023.4.8 hewanying P3870 [TJOI2009] 开关 分块*/
scanf("%d%d",&n,&m);
block=(int)floor(sqrt(n));
for(int i=1;i<=n;i++) id[i]=(i-1)/block+1,sum[id[i]]=0;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&op,&l,&r);
if(op==0) change(l,r);
else printf("%d\n",query(l,r));
}
return 0;
}
莫队算法
利用分块的思想,是一种对于离线区间询问
问题的暴力方法
判断能否使用莫队的因素
- 离线区间询问
- \(add\) 和 \(del\) 操作的复杂度必须是 \(O(1)\)
复杂度\(O(n\sqrt{n})\)
- 读取所有区间进行排序(按照 \(x,y\) 所在块的 \(id\) 进行从小到大的排序)
- 按照排序以后的顺序,对每个区间进行求解
- 按照原顺序输出答案
对于上一组操作 \([L1,R1]\),下一组操作是 \([L2,R2]\) 的话
(1,100),(2,2),(3,99),(4,4)
区间位移次数:\(99+98+96\)
(2,2),(4,4),(3,99)(1,100)
区间位移次数:\(4+96+3\)
bool cmp(const Node&a, const Node&b){
if ((a.x - 1) / block == (b.x - 1) / block) return a.y < b.y;
return a.x < b.x;
}
void add(int x){
vis[a[x]]++;
if (vis[a[x] == 1){
ans++;
}
}
void del(int x){
vis[a[x]]--;
if (vis[a[x]] == 0){
ans--;
}
}
int book[MAXN];
int main(){
int lastL, lastR, L, R;
scanf("%d%d", &n, &m);
block = sqrt(n);
for (int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; ++i){
scanf("%d%d", &Q[i].x, &Q[i].y);
Q[i].id = i;
}
sort(Q + 1, Q + n + 1, cmp);
int lastL = 0;
int lastR = 0;
for (int i = 1; i <= m; ++i){
int L = Q[i].x;
int R = Q[i].y;
// add 是先挪再改
// del 是先改再挪
while (lastL < L) del(lastL), lastL++;
while (lastL > L) lastL--, add(lastL);
while (lastR < R) lastR++, add(lastR);
while (lastR > R) del(lastR), lastR--;
if (ans == R - L + 1){
book[Q[i].id] = 1;
} else {
book[Q[i].id] = 0;
}
}
for (int i = 1; i <= m; ++i){
if (book[i])){
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
标签:分块,int,sum,算法,tag,lastR,操作,莫队,block
From: https://www.cnblogs.com/hewanying0622/p/17364057.html