数列分块入门（套题）（loj6277,loj6278,loj6279,loj6280,loj6281,loj6282,loj6283,loj6284,loj6285）

前言

zjoi考差了，码一些分块题缓解一下心情

壹

数列分块入门 1[loj6277]
题目大意：区间加，单点查
直接分块，区间加时完全覆盖的块打tag，边界块暴力重构
块大小设为n\sqrt nn​，复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq];
void clean(const int P)
{for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];tag[P]=0;
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;}for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)a[i]+=c;}else{for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c;clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;}}else print(a[r]+tag[belo[r]]),putchar('\n');}return flush(),0;
}

贰

数列分块入门 2[loj6278]
题目大意：区间加，区间查询小于某个数的个数
直接分块，区间加时完全覆盖的块打tag，边界块暴力重构
额外维护块内有序数组/平衡树，查询用lower_bound即可
块大小设为n\sqrt nn​，复杂度O(nnlogn)\mathcal O(n\sqrt{n}logn)O(nn​logn)
注意别忘了tag的影响
事实证明，写分块要注重常数，随便多点常数就会T
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq];
int v[sq][sq];
void clean(const int P)
{for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];tag[P]=0;
}
void rebuild(const int P)
{int top=0;for(rg int i=L[P];i<=R[P];i++)v[P][++top]=a[i];std::sort(v[P]+1,v[P]+top+1);
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;}for(rg int i=0;i<=belo[n];i++)size[i]=R[i]-L[i]+1,rebuild(i);for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)a[i]+=c;rebuild(belo[l]); }else{for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c;clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;rebuild(belo[l]),rebuild(belo[r]);}}else{c*=c;int ans=0;if(belo[l]==belo[r]){for(rg int i=l;i<=r;i++)ans+=(a[i]+tag[belo[l]])<c;}else{for(rg int i=belo[l]+1;i<belo[r];i++)ans+=std::lower_bound(v[i]+1,v[i]+size[i]+1,c-tag[i])-v[i]-1;for(rg int i=l;i<=R[belo[l]];i++)ans+=(a[i]+tag[belo[l]])<c;for(rg int i=r;i>=L[belo[r]];i--)ans+=(a[i]+tag[belo[r]])<c;}print(ans),putchar('\n');}}return flush(),0;
}

叁

数列分块入门 3[loj6279]
题目大意：区间加，区间查询小于某个数的最大数
与贰相似，只是这题取max而不是计数
块大小设为n\sqrt nn​，复杂度O(nnlogn)\mathcal O(n\sqrt{nlogn})O(nnlogn​)
这个垃圾数据范围比前两题多一倍，要复制的话记得改数组大小
注意一下lower_bound出来可能元素只有0个，此时应特判，否则加上tag的值可能会出错
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
const int maxn=100001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq];
int v[sq][sq];
void clean(const int P)
{for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];tag[P]=0;
}
void rebuild(const int P)
{int top=0;for(rg int i=L[P];i<=R[P];i++)v[P][++top]=a[i];std::sort(v[P]+1,v[P]+top+1);
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;}for(rg int i=0;i<=belo[n];i++)size[i]=R[i]-L[i]+1,rebuild(i),v[i][0]=-1;for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)a[i]+=c;rebuild(belo[l]); }else {for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c;clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;rebuild(belo[l]),rebuild(belo[r]);}}else{int ans=-1;if(belo[l]==belo[r]){for(rg int i=l;i<=r;i++)if((a[i]+tag[belo[l]])<c)maxd(ans,a[i]+tag[belo[l]]);}else{for(rg int i=belo[l]+1;i<belo[r];i++){const int val=v[i][std::lower_bound(v[i]+1,v[i]+size[i]+1,c-tag[i])-v[i]-1];if(val!=-1)maxd(ans,val+tag[i]);}for(rg int i=l;i<=R[belo[l]];i++)if((a[i]+tag[belo[l]])<c)maxd(ans,a[i]+tag[belo[l]]);for(rg int i=r;i>=L[belo[r]];i--)if((a[i]+tag[belo[r]])<c)maxd(ans,a[i]+tag[belo[r]]);}print(ans),putchar('\n');}}return flush(),0;
}

肆

数列分块入门 4[loj6280]
题目大意：区间加，区间求和
同壹，多记录一下块内和即可
块大小设为n\sqrt nn​，复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)
由于蜜汁数据范围，所以一些变量要开long long
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq];ll ans[sq];
void clean(const int P)
{for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];tag[P]=0;
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;}for(rg int i=1;i<=n;i++){size[belo[i]]++;ans[belo[i]]+=a[i];}for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)a[i]+=c;ans[belo[l]]+=(r-l+1)*c;}else{for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c,ans[i]+=size[i]*c;clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;ans[belo[l]]+=(R[belo[l]]-l+1)*c;ans[belo[r]]+=(r-L[belo[r]]+1)*c;}}else{ll res=0;if(belo[l]==belo[r]){for(rg int i=l;i<=r;i++)res+=a[i];res+=(r-l+1)*tag[belo[l]];}else{for(rg int i=belo[l]+1;i<belo[r];i++)res+=ans[i];for(rg int i=l;i<=R[belo[l]];i++)res+=a[i];for(rg int i=r;i>=L[belo[r]];i--)res+=a[i];res+=(R[belo[l]]-l+1)*tag[belo[l]];res+=(r-L[belo[r]]+1)*tag[belo[r]];}print(res%(c+1)),putchar('\n');}}return flush(),0;
}

伍

数列分块入门 5[loj6281]
题目大意：区间开根，区间求和
容易发现，一个2322^{32}232级别的数开$6$次根就是$1$了，那么直接维护块内是否都是$1$即可，如果都是$1$就不用做了
块大小设为n6\sqrt {\frac n6}6n​​，复杂度O(n6n)\mathcal O(n\sqrt{6n})O(n6n​)
调整块大小能优化一点复杂度
好像6本质上是loglogS（S是值域）
所以复杂度也可以写成O(nnloglogS)\mathcal O(n\sqrt{nloglogS})O(nnloglogS​)
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq],ans[sq];
void clean(const int P)
{if(tag[P])return;tag[P]=1;ans[P]=0;for(rg int i=L[P];i<=R[P];i++){a[i]=sqrt(a[i]);ans[P]+=a[i];if(a[i]!=1)tag[P]=0;}
}
int main()
{read(n),part=sqrt(n/6)+1;for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;size[belo[i]]++,ans[belo[i]]+=a[i];}for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){if(belo[l]==belo[r]){for(rg int i=l;i<=r;i++)ans[belo[l]]-=a[i],a[i]=sqrt(a[i]),ans[belo[l]]+=a[i];}else{for(rg int i=belo[l]+1;i<belo[r];i++)clean(i);for(rg int i=l;i<=R[belo[l]];i++)ans[belo[l]]-=a[i],a[i]=sqrt(a[i]),ans[belo[l]]+=a[i];for(rg int i=r;i>=L[belo[r]];i--)ans[belo[r]]-=a[i],a[i]=sqrt(a[i]),ans[belo[r]]+=a[i];}}else{int res=0;if(belo[l]==belo[r]){for(rg int i=l;i<=r;i++)res+=a[i];}else{for(rg int i=belo[l]+1;i<belo[r];i++)res+=ans[i];for(rg int i=l;i<=R[belo[l]];i++)res+=a[i];for(rg int i=r;i>=L[belo[r]];i--)res+=a[i];}print(res),putchar('\n');}}return flush(),0;
}

陆

数列分块入门 6[loj6282]
题目大意：单点添加数，单点查询
分块之后对于单点加数就直接在块内插入即可，复杂度O(n)\mathcal O(\sqrt n)O(n​)
我们发现，这样一来，访问一个位置也是O(n)\mathcal O(\sqrt n)O(n​)的复杂度
本题数据随机，到这里就做完了
实际不随机的时候有可能有些块过大使得复杂度退化到O(n2)\mathcal O(n^2)O(n2)
考虑重构
每插入n\sqrt nn​个数就对整个数组进行重构、重新分块，此处复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)
这样就保证了块大小始终是n\sqrt nn​级别的
块大小设为n\sqrt nn​，复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=200001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tot,val[sq][sq];
void ins(const int P,const int p,const int v)
{val[P][0]++;for(rg int i=val[P][0];i>p;i--)val[P][i]=val[P][i-1];val[P][p]=v;
}
void remake()
{int top=0;for(rg int i=0;val[i][0];i++){for(rg int j=1;j<=val[i][0];j++)a[++top]=val[i][j];val[i][0]=0;}for(rg int i=1;i<=top;i++){const int P=i/part;val[P][++val[P][0]]=a[i];}
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;val[P][++val[P][0]]=a[i];}for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){int his=0;for(rg int i=0;;i++)if(his+val[i][0]>=l){ins(i,l-his,r);break;}else his+=val[i][0];if(++tot==part)remake(),tot=0;}else{int his=0;for(rg int i=0;;i++)if(his+val[i][0]>=r){print(val[i][r-his]),putchar('\n');break;}else his+=val[i][0];}}return flush(),0;
}

柒

数列分块入门 7[loj6283]
题目大意：区间加，区间乘，单点查
同壹，额外维护乘的标记即可，可以把标记维护成x*a+b的形式，即要乘时需要将乘法、加法标记同时乘
块大小设为n\sqrt nn​，复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=100001,sq=1001,mod=10007;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],cheng[sq];
void clean(const int P)
{for(rg int i=L[P];i<=R[P];i++)a[i]=(a[i]*cheng[P]+tag[P])%mod;tag[P]=0,cheng[P]=1;
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]),a[i]%=mod;const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;cheng[P]=1;}for(rg int q=1;q<=n;q++){int opt,l,r,c;read(opt),read(l),read(r),read(c);if(opt==0){c%=mod;if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)a[i]=(a[i]+c)%mod;}else{for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]=(tag[i]+c)%mod;clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)a[i]=(a[i]+c)%mod;for(rg int i=r;i>=L[belo[r]];i--)a[i]=(a[i]+c)%mod;}}else if(opt==1){c%=mod;if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)a[i]=a[i]*c%mod;}else{for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]=tag[i]*c%mod,cheng[i]=cheng[i]*c%mod;clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)a[i]=a[i]*c%mod;for(rg int i=r;i>=L[belo[r]];i--)a[i]=a[i]*c%mod;}}else print((a[r]*cheng[belo[r]]+tag[belo[r]])%mod),putchar('\n');}return flush(),0;
}

捌

数列分块入门 8[loj6284]
题目大意：区间查询等于某个数的数量，并将这个区间赋值成这个数
分块，直接维护一个块里是否为同一个数、以及数的值即可，和伍很相似
块大小设为n\sqrt nn​，复杂度O(nnlogn)\mathcal O(n\sqrt{nlogn})O(nnlogn​)
code

#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=100001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],yes[sq],tag[sq],size[sq];
void clean(const int P)
{if(!yes[P])return;for(rg int i=L[P];i<=R[P];i++)a[i]=tag[P];yes[P]=0;
}
int main()
{read(n),part=sqrt(n);for(rg int i=1;i<=n;i++){read(a[i]);const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;size[belo[i]]++;}for(rg int q=1;q<=n;q++){int l,r,c,ans=0;read(l),read(r),read(c);if(belo[l]==belo[r]){clean(belo[l]);for(rg int i=l;i<=r;i++)if(a[i]==c)ans++;else a[i]=c;}else{for(rg int i=belo[l]+1;i<belo[r];i++)if(yes[i]){if(tag[i]==c)ans+=size[i];else tag[i]=c;}else{for(rg int j=L[i];j<=R[i];j++)ans+=a[j]==c;yes[i]=1,tag[i]=c;}clean(belo[l]),clean(belo[r]);for(rg int i=l;i<=R[belo[l]];i++)if(a[i]==c)ans++;else a[i]=c;for(rg int i=r;i>=L[belo[r]];i--)if(a[i]==c)ans++;else a[i]=c;}print(ans),putchar('\n');}return flush(),0;
}

玖

数列分块入门 9[loj6285]
题目大意：询问区间最小众数
直接分块，考虑维护出第$i$个块到第$j$个块的答案
此处复杂度为O(nn)\mathcal O(n\sqrt n)O(nn​)
对于一个询问
如果两个端点在同一块内直接暴力即可
否则答案一定在两个端点所在块内或者是中间块的答案
我们发现，中间的块的答案已经预处理好了
那么现在相当于有n\sqrt nn​个数，分别求出所有数在区间内的出现次数即可
可以预处理（可能还要个离散化）每种数的出现位置情况，二分即即可
我们观察复杂度，设块大小为P
复杂度为O(n2P+nPlogn)\mathcal O(\frac{n^2}{P}+nPlogn)O(Pn2​+nPlogn)
块大小设为nlogn\sqrt {\frac n{logn}}lognn​​，复杂度O(nnlogn)\mathcal O(n\sqrt{nlogn})O(nnlogn​)
update：
这里给出的做法是空间复杂度$\mathcal{O}(n)$，时间复杂度O(nnlogn)\mathcal O(n\sqrt{nlogn})O(nnlogn​)的
离线做法（莫队）可以做到空间复杂度$\mathcal{O}(n)$，时间复杂度O(nn)\mathcal O(n\sqrt{n})O(nn​)
这个在线做法用分块代替二分可以做到空间复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)，时间复杂度O(nn)\mathcal O(n\sqrt n)O(nn​)
code

#include
#include
#include
#include
#include
#include
#define rg register
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=100001,sq=10001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],ans[sq][sq];
int lsh[maxn],tot;
std::vector<int>p[maxn];
int tim[maxn];
int find(const int x)
{return std::lower_bound(lsh+1,lsh+tot+1,x)-lsh;
}
int count(const int l,const int r,const int x)
{int LL,RR,FI=-1,SE=-1;LL=0,RR=p[x].size()-1;while(LL<=RR){const int mid=(LL+RR)>>1;if(p[x][mid]<=r)FI=mid,LL=mid+1;else RR=mid-1;}LL=0,RR=p[x].size()-1;while(LL<=RR){const int mid=(LL+RR)>>1;if(p[x][mid]<l)SE=mid,LL=mid+1;else RR=mid-1;}return FI-SE;
}
int main()
{read(n),part=80;for(rg int i=1;i<=n;i++){read(a[i]),lsh[i]=a[i];const int P=i/part;belo[i]=P;if(!L[P])L[P]=i;R[P]=i;}std::sort(lsh+1,lsh+n+1);tot=std::unique(lsh+1,lsh+n+1)-lsh-1;for(rg int i=1;i<=n;i++)p[a[i]=find(a[i])].push_back(i);for(rg int i=0;i<=belo[n];i++){int res=0,mx=0;for(rg int j=i;j<=belo[n];j++){for(rg int k=L[j];k<=R[j];k++){tim[a[k]]++;if(tim[a[k]]>mx||tim[a[k]]==mx&&a[k]<res)mx=tim[a[k]],res=a[k];}ans[i][j]=res;}memset(tim,0,sizeof(tim));}for(rg int q=1;q<=n;q++){int l,r,mx=0,res=0;read(l),read(r);if(belo[r]-belo[l]<=1){for(rg int i=l;i<=r;i++){tim[a[i]]++;if(tim[a[i]]>mx||tim[a[i]]==mx&&a[i]<res)mx=tim[a[i]],res=a[i];}for(rg int i=l;i<=r;i++)tim[a[i]]--;}else{mx=count(l,r,ans[belo[l]+1][belo[r]-1]),res=ans[belo[l]+1][belo[r]-1];for(rg int i=l;i<=R[belo[l]];i++){const int T=count(l,r,a[i]);if(T>mx||T==mx&&a[i]<res)mx=T,res=a[i];}for(rg int i=r;i>=L[belo[r]];i--){const int T=count(l,r,a[i]);if(T>mx||T==mx&&a[i]<res)mx=T,res=a[i];}}print(lsh[res]),putchar('\n');}return flush(),0;
}

总结

有些题有细节写的不对就会被卡，写这9题也算提升一下代码能力了吧
同时对分块的印象更深刻了

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！