[分块] 分块练习九例
LOJ 6277~6285T1 Block1区间加,单点查#include<bits/stdc++.h>using namespace std;#define in Read()int in{int i=0,f=1;char ch=0;while(!isdigit(ch)&&ch!='-') ch=getchar();if(ch=='-') ch=getchar(),f
LOJ 6277~6285
6277
T1 Block1
区间加,单点查
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
const int N=5e4+5;
int n,a[N],sz,bl[N],st[N],ed[N],block,add[N];
void modify(int l,int r,int c){
int p=bl[l],q=bl[r];
if(p==q){
for(int i=l;i<=r;++i) a[i]+=c;
return;
}else{
for(int i=p+1;i<=q-1;++i) add[i]+=c;
for(int i=l;i<=ed[p];++i) a[i]+=c;
for(int i=st[q];i<=r;++i) a[i]+=c;
return;
}
}
int main(){
n=in;
for(int i=1;i<=n;++i) a[i]=in;
sz=sqrt(n);
block=n/sz;
if(n%sz) ++block;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
for(int i=1;i<=block;++i) st[i]=(i-1)*sz+1,ed[i]=i*sz;
ed[block]=min(ed[block],n);
for(int i=1;i<=n;++i){
int opt=in,l=in,r=in,c=in;
if(!opt) modify(l,r,c);
else printf("%d\n",a[r]+add[bl[r]]);
}
return 0;
}
T2 Block2
分块不一定分
n
\sqrt n
n,可以通过计算得到更优的块
如利用均值不等式证明等
区间加,查询小于某个值的元素个数
为了降低查询复杂度,要求块内元素有序,二分
注意不能对原序列排序
计算ed
时保证ed<n
整块元素不用重排
零散元素加了重排
O
(
n
n
log
n
)
O(n\sqrt n\log\sqrt n)
O(nnlogn)
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
#define pb push_back
#define st(x) ((x-1)*sz+1)
#define ed(x) (x*sz)
const int N=1e5+5;
int n,sz,blk,add[N],bl[N],a[N];
vector<int>s[N];
void reset(int x){
s[x].clear();
for(int i=st(x);i<=min(ed(x),n);++i) s[x].pb(a[i]);
sort(s[x].begin(),s[x].end());
}
void modify(int l,int r,int c){
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i) a[i]+=c;
reset(bl[l]);
return;
}else{
for(int i=l;i<=ed(bl[l]);++i) a[i]+=c;
reset(bl[l]);
for(int i=bl[l]+1;i<=bl[r]-1;++i) add[i]+=c;
for(int i=st(bl[r]);i<=r;++i) a[i]+=c;
reset(bl[r]);
return;
}
}
int query(int l,int r,int c){
int ans=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i) if(a[i]+add[bl[l]]<c) ++ans;
return ans;
}else{
for(int i=l;i<=ed(bl[l]);++i) if(a[i]+add[bl[l]]<c) ++ans;
for(int i=bl[l]+1;i<=bl[r]-1;++i)
ans+=lower_bound(s[i].begin(),s[i].end(),c-add[i])-s[i].begin();
for(int i=st(bl[r]);i<=r;++i) if(a[i]+add[bl[r]]<c) ++ans;
return ans;
}
}
int main(){
n=in,sz=sqrt(n),blk=n/sz;
if(n%sz) ++blk;
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,s[bl[i]].pb(a[i]);
for(int i=1;i<=blk;++i) sort(s[i].begin(),s[i].end());
for(int i=1;i<=n;++i){
int op=in,l=in,r=in,c=in;
if(!op) modify(l,r,c);
else printf("%d\n",query(l,r,c*c));
}
return 0;
}
T3 Block3
区间加,查询某个值的前驱(小于它的最大值)
取max
,还是要lower_bound
48行符号搞清楚了:>=
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
#define pb push_back
#define st(x) ((x-1)*sz+1)
#define ed(x) (x*sz)
const int N=1e5+5;
int n,sz,blk,bl[N],a[N],add[N];
vector<int>s[N];
void reset(int x){
s[x].clear();
for(int i=st(x);i<=min(ed(x),n);++i) s[x].pb(a[i]);
sort(s[x].begin(),s[x].end());
}
void modify(int l,int r,int c){
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i) a[i]+=c;
reset(bl[l]);
return;
}else{
for(int i=l;bl[i]==bl[l];++i) a[i]+=c;
reset(bl[l]);
for(int i=bl[l]+1;i<=bl[r]-1;++i) add[i]+=c;
for(int i=r;bl[i]==bl[r];--i) a[i]+=c;
reset(bl[r]);
return;
}
}
int query(int l,int r,int c){
int ans=-1;
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i) if(a[i]+add[bl[l]]<c) ans=max(ans,a[i]+add[bl[l]]);
return ans;
}else{
for(int i=l;bl[i]==bl[l];++i) if(a[i]+add[bl[l]]<c) ans=max(ans,a[i]+add[bl[l]]);
for(int i=bl[l]+1;i<=bl[r]-1;++i){
if(s[i].front()>=c-add[i]) continue;
if(s[i].back()<c-add[i]){
ans=max(ans,s[i].back()+add[i]);
continue;
}
int w=lower_bound(s[i].begin(),s[i].end(),c-add[i])-s[i].begin()-1;
ans=max(ans,s[i][w]+add[i]);
}
for(int i=r;bl[i]==bl[r];--i) if(a[i]+add[bl[r]]<c) ans=max(ans,a[i]+add[bl[r]]);
return ans;
}
}
int main(){
n=in,sz=sqrt(n),blk=n/sz;
if(n%sz) ++blk;
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,s[bl[i]].pb(a[i]);
for(int i=1;i<=blk;++i) sort(s[i].begin(),s[i].end());
for(int i=1;i<=n;++i){
int op=in,l=in,r=in,c=in;
if(!op) modify(l,r,c);
else printf("%d\n",query(l,r,c));
}
}
T4 Block4
区间加,区间和
一定要开long long
打码5分钟,debug2小时
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
const int N=1e6+5;
int n,sz,a[N],add[N],blk,bl[N],sum[N];
void modify(int l,int r,int c){
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i) a[i]+=c,sum[bl[i]]+=c;
return;
}else{
for(int i=l;bl[i]==bl[l];++i) a[i]+=c,sum[bl[i]]+=c;
for(int i=bl[l]+1;i<=bl[r]-1;++i) add[i]+=c,sum[i]+=c*sz;
for(int i=r;bl[i]==bl[r];--i) a[i]+=c,sum[bl[i]]+=c;
}
}
int query(int l,int r,int mod){
int ans=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i)
(ans+=a[i]+add[bl[i]])%=mod;
return ans;
}else{
for(int i=l;bl[i]==bl[l];++i) (ans+=a[i]+add[bl[i]])%=mod;
for(int i=bl[l]+1;i<=bl[r]-1;++i) (ans+=sum[i])%=mod;
for(int i=r;bl[i]==bl[r];--i) (ans+=a[i]+add[bl[i]])%=mod;
return ans%mod;
}
}
signed main(){
n=in,sz=sqrt(n),blk=n/sz;
if(n%sz) ++blk;
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,sum[bl[i]]+=a[i];
for(int i=1;i<=n;++i){
int op=in,l=in,r=in,c=in;
if(!op) modify(l,r,c);
else printf("%lld\n",query(l,r,c+1));
}
return 0;
}
T5 Block5
区间开方,区间求和
发现0/1开方不变,其余数最多开31次方就会变成0/1
维护全0/1区间即可
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
const int N=5e4+5;
int n,sz,blk,a[N],sum[N],bl[N];
bool tag[N];
int Sqrt(int x){
return x?sqrt(x):0;
}
void change(int x){
if(tag[x]) return;
int l=(x-1)*sz+1,r=min(x*sz,n);
bool flag=false;
for(int i=l;i<=r;++i){
sum[x]-=a[i];
a[i]=Sqrt(a[i]);
sum[x]+=a[i];
if(a[i]!=0&&a[i]!=1) flag=true;
}
tag[x]=flag^1;
}
void modify(int l,int r){
if(bl[l]==bl[r]){
if(tag[bl[l]]) return;
for(int i=l;i<=r;++i){
sum[bl[i]]-=a[i];
a[i]=Sqrt(a[i]);
sum[bl[i]]+=a[i];
}
return;
}
if(!tag[bl[l]])
for(int i=l;bl[i]==bl[l];++i){
sum[bl[i]]-=a[i];
a[i]=Sqrt(a[i]);
sum[bl[i]]+=a[i];
}
for(int i=bl[l]+1;i<=bl[r]-1;++i) change(i);
if(!tag[bl[r]])
for(int i=r;bl[i]==bl[r];--i){
sum[bl[i]]-=a[i];
a[i]=Sqrt(a[i]);
sum[bl[i]]+=a[i];
}
return;
}
int query(int l,int r){
int ans=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i) ans+=a[i];
return ans;
}else{
for(int i=l;bl[i]==bl[l];++i) ans+=a[i];
for(int i=bl[l]+1;i<=bl[r]-1;++i) ans+=sum[i];
for(int i=r;bl[i]==bl[r];--i) ans+=a[i];
return ans;
}
}
signed main(){
n=in,sz=Sqrt(n),blk=n/sz;
if(n%sz) ++blk;
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,sum[bl[i]]+=a[i];
for(int i=1;i<=n;++i){
int op=in,l=in,r=in,c=in;
if(!op) modify(l,r);
else printf("%lld\n",query(l,r));
}
return 0;
}
T6 Block6
单点插单点询问
- 分块是暴力算法
- 块大小你决定
块太大了重新分块
51行s[id][p-num-1]
是因为vector
下标[0,size()-1]
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
#define pb push_back
const int N=1e6+5;
int n,sz,blk,bl[N],a[N];
vector<int>s[N];
void rebuild(){
int id=0,cnt=0;
while(!s[id+1].empty()){
++id;
for(int i=0;i<s[id].size();++i) a[++cnt]=s[id][i];
s[id].clear();
}
sz=sqrt(cnt);
for(int i=1;i<=cnt;++i){
bl[i]=(i-1)/sz+1;
s[bl[i]].pb(a[i]);
}
return;
}
void insert(int p,int v){
int id=0,num=0;
while(num+s[id+1].size()<p){
++id;
num+=s[id].size();
}
++id;
s[id].insert(p-num-1+s[id].begin(),v);
if(s[id].size()>=20*sz) rebuild();
return;
}
int query(int p){
int id=0,num=0;
while(num+s[id+1].size()<p){
++id;
num+=s[id].size();
}
++id;
return s[id][p-num-1];
}
int main(){
n=in,sz=sqrt(n);
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,s[bl[i]].pb(a[i]);
for(int i=1;i<=n;++i){
int op=in,l=in,r=in,c=in;
if(!op) insert(l,r);
else printf("%d\n",query(r));
}
return 0;
}
T7 Block7
单点乘,单点加,单点查
线段树2
乘法优先
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
#define debug puts("qwq")
const int N=1e5+5,mod=1e4+7;
int n,sz,bl[N],a[N],plu[N],tim[N],blk;
int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int mul(int a,int b){return 1ll*a*b%mod;}
void push_down(int b){
for(int i=(b-1)*sz+1;bl[i]==b;++i)
a[i]=add(mul(a[i],tim[b]),plu[b]);
tim[b]=1;plu[b]=0;
return;
}
void modify_add(int l,int r,int c){
if(bl[l]==bl[r]){
push_down(bl[l]);
for(int i=l;i<=r;++i)
a[i]=add(a[i],c);
return;
}else{
push_down(bl[l]);
push_down(bl[r]);
for(int i=l;bl[i]==bl[l];++i)
a[i]=add(a[i],c);
for(int i=bl[l]+1;i<=bl[r]-1;++i)
plu[i]=add(plu[i],c);
for(int i=r;bl[i]==bl[r];--i)
a[i]=add(a[i],c);
return;
}
}
void modify_mul(int l,int r,int c){
if(bl[l]==bl[r]){
push_down(bl[l]);
for(int i=l;i<=r;++i)
a[i]=mul(a[i],c);
return;
}else{
push_down(bl[l]);
push_down(bl[r]);
for(int i=l;bl[i]==bl[l];++i)
a[i]=mul(a[i],c);
for(int i=bl[l]+1;i<=bl[r]-1;++i)
tim[i]=mul(tim[i],c),
plu[i]=mul(plu[i],c);
for(int i=r;bl[i]==bl[r];--i)
a[i]=mul(a[i],c);
return;
}
}
int query(int p){
push_down(bl[p]);
return a[p];
}
int main(){
n=in,sz=sqrt(n),blk=n/sz;
if(n%sz) ++blk;
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
for(int i=1;i<=blk;++i) tim[i]=1;
for(int i=1;i<=n;++i){
int op=in,l=in,r=in,c=in;
if(op==0) modify_add(l,r,c);
else if(op==1) modify_mul(l,r,c);
else printf("%d\n",query(r));
}
return 0;
}
T8 Block8
区间改区间查
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
const int N=1e5+5;
int n,sz,blk,a[N],tag[N],bl[N];
void push_down(int b){
if(tag[b]==-1) return;
for(int i=(b-1)*sz+1;bl[i]==b;++i)
a[i]=tag[b];
tag[b]=-1;
}
int query(int l,int r,int c){
int ans=0;
if(bl[l]==bl[r]){
push_down(bl[l]);
for(int i=l;i<=r;++i){
if(a[i]==c) ++ans;
a[i]=c;
}
return ans;
}else{
push_down(bl[l]);
push_down(bl[r]);
for(int i=l;bl[i]==bl[l];++i)
if(a[i]==c) ++ans;
else a[i]=c;
for(int i=r;bl[i]==bl[r];--i)
if(a[i]==c) ++ans;
else a[i]=c;
for(int i=bl[l]+1;i<=bl[r]-1;++i){
if(tag[i]==-1){
for(int j=(i-1)*sz+1;bl[j]==i;++j)
if(a[j]==c) ++ans;
else a[j]=c;
tag[i]=c;
}else{
if(tag[i]==c) ans+=sz;
else tag[i]=c;
}
}
return ans;
}
}
int main(){
n=in,sz=sqrt(n);
for(int i=1;i<=n;++i) a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
for(int i=1;i<=n;i+=sz) tag[bl[i]]=-1;
for(int i=1;i<=n;++i){
int l=in,r=in,c=in;
printf("%d\n",query(l,r,c));
}
return 0;
}
T9 Block9
蒲公英
求最小众数
蒲公英掉紫了😭
黑色经验-1
n
≤
4
e
4
,
a
i
≤
1
e
9
n\le 4e4,a_i\le 1e9
n≤4e4,ai≤1e9,离散化
竟然不带修,多美好的世界
预处理
s
i
,
j
s_{i,j}
si,j表示第
i
i
i块中
j
j
j的出现次数
p
i
,
j
p_{i,j}
pi,j表示第
i
i
i块到第
j
j
j块的众数
那么 [ l , r ] [l,r] [l,r]的众数为整块众数和散装中数的并集,统计这些数个数即可
用桶统计,
p
o
t
[
i
]
≤
2
n
+
1
pot[i]\le 2\sqrt n+1
pot[i]≤2n+1
整块类前缀和,
O
(
1
)
O(1)
O(1);总查询
O
(
n
)
O(\sqrt n)
O(n)
预处理:
s
i
,
j
s_{i,j}
si,j前缀和
p
i
,
j
p_{i,j}
pi,j,枚举
i
,
j
i,j
i,j,利用
s
i
,
j
s_{i,j}
si,j更新
#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
int i=0,f=1;char ch=0;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=-1;
while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
return i*f;
}
#define pb push_back
const int N=1e5+5,M=1e3+5,inf=2147483647;
int n,sz,lim;
int bl[N],a[N],val[N];
int s[M][N],p[M][M];
int pot[N];
vector<int>inpot;
void discretize(){
sort(a+1,a+n+1);
int len=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;++i){
val[i]=lower_bound(a+1,a+n+1,val[i])-a;
lim=max(lim,val[i]);
}
return;
}
void prepare(){
for(int i=1;i<=n;++i)
++s[bl[i]][val[i]];
for(int i=1;i<=bl[n];++i)
for(int j=1;j<=lim;++j)
s[i][j]+=s[i-1][j];
for(int i=1;i<=bl[n];++i)
for(int j=i;j<=bl[n];++j){
int mode=inf,cnt=0;
for(int k=(j-1)*sz+1;bl[k]==j;++k){
if(cnt<s[j][val[k]]-s[i-1][val[k]]){
cnt=s[j][val[k]]-s[i-1][val[k]];
mode=val[k];
}
if(cnt==s[j][val[k]]-s[i-1][val[k]]&&mode>val[k])
mode=val[k];
}
if(i!=j){
int k=p[i][j-1];
if(cnt<s[j][k]-s[i-1][k]){
mode=k;
cnt=s[j][k]-s[i-1][k];
}
if(cnt==s[j][k]-s[i-1][k]&&mode>k)
mode=k;
}
p[i][j]=mode;
}
return;
}
int query(int l,int r){
if(!inpot.empty()){
for(int i=0;i<inpot.size();++i)
pot[inpot[i]]=0;
inpot.clear();
}
int mode=inf,cnt=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i){
++pot[val[i]];
if(pot[val[i]]>cnt){
cnt=pot[val[i]];
mode=val[i];
}
if(pot[val[i]]==cnt&&mode>val[i])
mode=val[i];
inpot.pb(val[i]);
}
return mode;
}else{
for(int i=l;bl[i]==bl[l];++i){
if(!pot[val[i]])
pot[val[i]]+=s[bl[r]-1][val[i]]-s[bl[l]][val[i]];
pot[val[i]]++;
if(pot[val[i]]>cnt){
cnt=pot[val[i]];
mode=val[i];
}
if(pot[val[i]]==cnt&&mode>val[i])
mode=val[i];
inpot.pb(val[i]);
}
for(int i=r;bl[i]==bl[r];--i){
if(!pot[val[i]])
pot[val[i]]+=s[bl[r]-1][val[i]]-s[bl[l]][val[i]];
pot[val[i]]++;
if(pot[val[i]]>cnt){
cnt=pot[val[i]];
mode=val[i];
}
if(pot[val[i]]==cnt&&mode>val[i])
mode=val[i];
inpot.pb(val[i]);
}
if(bl[r]==bl[l]+1) return mode;
int mone=p[bl[l]+1][bl[r]-1];
if(pot[mone]) return mode;
pot[mone]+=s[bl[r]-1][mone]-s[bl[l]][mone];
if(pot[mone]>cnt){
mode=mone;
cnt=pot[mone];
}
if(pot[mone]==cnt&&mone<mode)
mode=mone;
inpot.pb(mone);
return mode;
}
}
int main(){
n=in,sz=sqrt(n);
for(int i=1;i<=n;++i) val[i]=a[i]=in;
for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
discretize();
prepare();
for(int i=1;i<=n;++i){
int l=in,r=in;
printf("%d\n",a[query(l,r)]);
}
return 0;
}
其余练习
更多推荐
所有评论(0)