[关闭]
@11101001 2018-03-11T02:16:46.000000Z 字数 10610 阅读 947

数列分块1-9

偷懒QAQ

题目链接

loj的数列分块如门1-9

这算是题解了吧

题解的话
我就不说了吧
毕竟，黄学长的博客里已经说得
很清楚了
吧2333(我真是废QAQ
.........Hzwer传送门

代码

数列分块1

  1. #include<cmath>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. int n,m;
  6. inline int read() { 
  7.     int x=0,f=1;
  8.     char c=getchar();
  9.     while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
  10.     while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
  11.     return x*f;
  12. }
  13. const int maxn = 100007;
  14. int a[maxn],bl[maxn],tag[maxn],size;
  15. void modify(int aa,int b,int c) {
  16.     for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c;
  17.     if(bl[aa]!=bl[b])
  18.         for(int i=(bl[b]-1)*size+1;i<=b;++i)a[i]+=c;
  19.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) tag[i]+=c;
  20. }
  21. int main()  {
  22.     n=read(),size=sqrt(n);
  23.     for(int i=1;i<=n;++i) a[i]=read();
  24.     for(int i=1;i<=n;++i) bl[i]=(i-1)/size+1;
  25.     for(int  op,aa,b,c,i=1;i<=n;++i) {
  26.         op=read(),aa=read(),b=read(),c=read();
  27.         if(!op)modify(aa,b,c);
  28.         else printf("%d\n",a[b]+tag[bl[b]]);
  29.     }
  30.     return 0;
  31. }

数列分块2

  1. #include<cmath>
  2. #include<vector>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. using std::vector;
  7. vector<int>vec[100086];
  8. int n,m;
  9. inline int read() { 
  10.     int x=0,f=1;
  11.     char c=getchar();
  12.     while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
  13.     while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
  14.     return x*f;
  15. }
  16. const int maxn = 100007;
  17. int a[maxn],bl[maxn],tag[maxn],size;
  18. void update(int x) {
  19.     vec[x].clear();
  20.     for(int i=(x-1)*size+1;i<=std::min(x*size,n);++i)
  21.         vec[x].push_back(a[i]);
  22.     std::sort(vec[x].begin(),vec[x].end());
  23. }
  24. void modify(int aa,int b,int c) {
  25.     for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c;
  26.     update(bl[aa]);
  27.     if(bl[aa]!=bl[b]) {
  28.         for(int i=(bl[b]-1)*size+1;i<=b;++i)a[i]+=c;
  29.         update(bl[b]);
  30.     }
  31.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) tag[i]+=c;
  32. }
  33. int query(int aa,int b,int c) {
  34.     int ans=0;c*=c;
  35.     for(int i=aa;i<=std::min(b,bl[aa]*size);++i) 
  36.         if(a[i]+tag[bl[aa]]<c)ans++;
  37.     if(bl[aa]!=bl[b]) 
  38.         for(int i=(bl[b]-1)*size+1;i<=b;++i)
  39.             if(a[i]+tag[bl[b]]<c)ans++;
  40.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) {
  41.         int x=c-tag[i];
  42.         ans+=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin();
  43.     }
  44.     return ans;
  45. }
  46. int main()  {
  47.     n=read(),size=sqrt(n);
  48.     for(int i=1;i<=n;++i) a[i]=read();
  49.     for(int i=1;i<=n;++i) bl[i]=((i-1)/size+1),vec[bl[i]].push_back(a[i]);
  50.     for(int i=1;i<=bl[n];i++)std::sort(vec[i].begin(),vec[i].end());    
  51.     for(int  op,aa,b,c,i=1;i<=n;++i) {
  52.         op=read(),aa=read(),b=read(),c=read();
  53.         if(!op)modify(aa,b,c);
  54.         else printf("%d\n",query(aa,b,c));
  55.     }
  56.     return 0;
  57. }

数列分块3

  1. #include<cmath>
  2. #include<vector>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. using std::vector;
  7. vector<int>vec[100086];
  8. int n,m;
  9. inline int read() { 
  10.     int x=0,f=1;
  11.     char c=getchar();
  12.     while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
  13.     while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
  14.     return x*f;
  15. }
  16. const int maxn = 100007;
  17. int a[maxn],bl[maxn],tag[maxn],size;
  18. void update(int x) {
  19.     vec[x].clear();
  20.     for(int i=(x-1)*size+1;i<=std::min(x*size,n);++i)
  21.         vec[x].push_back(a[i]);
  22.     std::sort(vec[x].begin(),vec[x].end());
  23. }
  24. void modify(int aa,int b,int c) {
  25.     for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c;
  26.     update(bl[aa]);
  27.     if(bl[aa]!=bl[b]) {
  28.         for(int i=(bl[b]-1)*size+1;i<=b;++i)a[i]+=c;
  29.         update(bl[b]);
  30.     }
  31.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) 
  32.         tag[i]+=c;
  33. }
  34. int query(int aa,int b,int c) {
  35.     int tmp,ret=-1,retc=0x3f3f3f3f;
  36.     for(int i=aa;i<=std::min(b,bl[aa]*size);++i) 
  37.         if(c>a[i]+tag[bl[aa]]) {
  38.             tmp=(c-(a[i]+tag[bl[aa]]));
  39.             if(tmp<retc) retc=tmp,ret=a[i]+tag[bl[aa]];
  40.         }
  41.         //if(a[i]+tag[bl[aa]]>=c)return a[i-1];
  42.     if(bl[aa]!=bl[b]) 
  43.         for(int i=(bl[b]-1)*size+1;i<=b;++i)
  44.             if(c>a[i]+tag[bl[b]]) {
  45.                 tmp=(c-(a[i]+tag[bl[b]]));
  46.                 if(tmp<retc) retc=tmp,ret=a[i]+tag[bl[b]];
  47.             }
  48.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) {
  49.         int x=c-tag[i];
  50.         int loc=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin()-1;
  51.         if(loc<0)continue;
  52.         tmp=c-vec[i][loc]-tag[i];
  53.         if(tmp<retc) retc=tmp,ret=vec[i][loc]+tag[i];
  54.     }
  55.     return ret;
  56. }
  57. int main()  {
  58.     //std::cin>>a;std::cout<<a;
  59.     n=read(),size=sqrt(n);
  60.     for(int i=1;i<=n;++i) a[i]=read();
  61.     for(int i=1;i<=n;++i) bl[i]=((i-1)/size+1),vec[bl[i]].push_back(a[i]);
  62.     for(int i=1;i<=bl[n];i++)std::sort(vec[i].begin(),vec[i].end());    
  63.     for(int  op,aa,b,c,i=1;i<=n;++i) {
  64.         op=read(),aa=read(),b=read(),c=read();
  65.         if(!op)modify(aa,b,c);
  66.         else printf("%d\n",query(aa,b,c));
  67.     }
  68.     return 0;
  69. }
  70. /*
  71. 6
  72. 123 321 245 654 232 233
  73. 1 2 5 246
  74. 0 2 4 666
  75. 1 1 6 888
  76. */

数列分块4

  1. #include<cmath>
  2. #include<vector>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. int n,m;
  7. inline int read() { 
  8.     int x=0,f=1;
  9.     char c=getchar();
  10.     while(c<'0'||c>'9') {if(c=='0')f=-1;c=getchar();}
  11.     while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
  12.     return x*f;
  13. }
  14. const int maxn = 100007;
  15. long long  a[maxn];int bl[maxn],size;
  16. long long tag[maxn],sum[maxn];
  17. void modify(int aa,int b,int c) {
  18.     for(int i=aa;i<=std::min(bl[aa]*size,b);++i) a[i]+=c,sum[bl[i]]+=c;//,[bl[a]]+=c;
  19.     if(bl[aa]!=bl[b]) 
  20.         for(int i=(bl[b]-1)*size+1;i<=b;++i) a[i]+=c,sum[bl[i]]+=c;//,tag[bl[b]]+=c;
  21.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) 
  22.         tag[i]+=c;
  23. }
  24. long long  query(int aa,int b,int c) {
  25.     long long ans=0;
  26.     for(int i=aa;i<=std::min(b,bl[aa]*size);++i) 
  27.         ans+=a[i]+tag[bl[aa]];
  28.     if(bl[aa]!=bl[b]) 
  29.         for(int i=(bl[b]-1)*size+1;i<=b;++i)
  30.             ans+=a[i]+tag[bl[b]];
  31.     for(int i=bl[aa]+1;i<=bl[b]-1;++i) {
  32.         ans+=sum[i]+tag[i]*size;
  33.     }
  34.     return ans%c;
  35. }
  36. int main()  {
  37.     //std::cin>>a;std::cout<<a;
  38.     n=read(),size=sqrt(n);
  39.     for(int i=1;i<=n;++i) a[i]=read();
  40.     for(int i=1;i<=n;++i) bl[i]=((i-1)/size+1),sum[bl[i]]+=a[i];
  41.     for(int  op,aa,b,c,i=1;i<=n;++i) {
  42.         op=read(),aa=read(),b=read(),c=read();
  43.         if(!op)modify(aa,b,c);
  44.         else printf("%d\n",query(aa,b,c+1));
  45.     }
  46.     return 0;
  47. }
  48. /*
  49. 6
  50. 123 321 245 654 232 233
  51. 1 2 5 246
  52. 0 2 4 666
  53. 1 1 6 888
  54. */

数列分块5

  1. #include<cmath>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using std::min;
  5. inline int read() {
  6.     int  x=0,op=1;char c=getchar();
  7.     while(c<'0'||c>'9'){if(c=='-')op=-1;c=getchar();}
  8.     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
  9.     return x*op;
  10. }
  11. const int maxn = 100007;
  12. int n,size;
  13. int bl[maxn],a[maxn],sum[maxn],tag[maxn];
  14. inline void update(int x) {
  15.     if(tag[x])return;
  16.     tag[x]=1,sum[x]=0;
  17.     for(int i=(x-1)*size+1;i<=x*size;i++) {
  18.         a[i]=sqrt(a[i]),sum[x]+=a[i];
  19.         if(a[i]>1)tag[x]=0;
  20.     }
  21. }
  22. void add(int l,int r) {
  23.     for(int i=l;i<=min(bl[l]*size,r);i++)
  24.         sum[bl[l]]-=a[i],a[i]=sqrt(a[i]),sum[bl[l]]+=a[i];
  25.     if(bl[l]!=bl[r])
  26.         for(int i=(bl[r]-1)*size+1;i<=r;i++)
  27.             sum[bl[r]]-=a[i],a[i]=sqrt(a[i]),sum[bl[r]]+=a[i];
  28.     for(int i=bl[l]+1;i<=bl[r]-1;i++)
  29.         update(i);
  30. }
  31. int query(int l,int r) {
  32.     int ans=0;
  33.     for(int i=l;i<=min(bl[l]*size,r);i++) ans+=a[i];
  34.     if(bl[l]!=bl[r])
  35.         for(int i=(bl[r]-1)*size+1;i<=r;i++)
  36.             ans+=a[i];
  37.     for(int i=bl[l]+1;i<=bl[r]-1;i++)
  38.         ans+=sum[i];
  39.     return ans;
  40. }
  41. int main() {
  42.     n=read();size=sqrt(n);
  43.     for(int i=1;i<=n;i++)a[i]=read();
  44.     for(int i=1;i<=n;i++) 
  45.         bl[i]=(i-1)/size+1,sum[bl[i]]+=a[i];
  46.     for(int op,a,b,c,i=1;i<=n;i++) {
  47.         op=read(),a=read(),b=read(),c=read();
  48.         if(!op)add(a,b);
  49.         else printf("%d\n",query(a,b));
  50.     }
  51.     return 0;
  52. }

数列分块6

  1. #include<cmath>
  2. #include<vector>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using std::vector;
  6. const int maxn = 100007;
  7. inline int read() {
  8.     int x=0,f=1;char c=getchar();
  9.     while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
  10.     while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
  11.     return x*f;
  12. }
  13. vector<int>vec[maxn];
  14. int a[maxn],bl[maxn],size,n;
  15. void insert(int loc,int w) {
  16.     for(int i=1;i<=bl[n];++i) {
  17.         if(loc<=vec[i].size()) {vec[i].insert(vec[i].begin()+loc-1,w);return;}
  18.         loc-=vec[i].size();
  19.     }
  20. }
  21. int query(int loc) {
  22.     for(int i=1;i<=bl[n];++i) {
  23.         if(loc<=vec[i].size()) return vec[i][loc-1];
  24.         loc-=vec[i].size();
  25.     }
  26. }
  27. int main() {
  28.     n=read();size=sqrt(n);
  29.     for(int i=1;i<=n;++i)a[i]=read();
  30.     for(int i=1;i<=n;++i)bl[i]=(i-1)/size+1,vec[bl[i]].push_back(a[i]);
  31.     for(int op,aa,b,c,i=1;i<=n;++i) {
  32.         op=read(),aa=read(),b=read(),c=read();
  33.         if(!op) insert(aa,b);
  34.         else printf("%d\n",query(b));
  35.     }
  36. }

数列分块7

  1. #include<cmath>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define mod 10007
  6. using std::min;
  7. const int maxn = 100007;
  8. inline int read() {
  9.     int x=0,f=1;char c=getchar();
  10.     while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
  11.     while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
  12.     return x*f;
  13. }
  14. int tagm[maxn],taga[maxn];
  15. int a[maxn],bl[maxn],size,n;
  16. void reset(int x) {
  17.     for(int i=(x-1)*size+1;i<=min(n,x*size);i++)
  18.         a[i]=(a[i]*tagm[x]+taga[x])%mod;
  19.     taga[x]=0;tagm[x]=1;
  20. }
  21. void Modify_Add(int l,int r,int w) {
  22.     reset(bl[l]);
  23.     for(int i=l;i<=min(r,bl[l]*size);++i) a[i]+=w,a[i]%=mod;
  24.     if(bl[l]!=bl[r]) {
  25.         reset(bl[r]);
  26.         for(int i=(bl[r]-1)*size+1;i<=r;++i) 
  27.             a[i]+=w,a[i]%=mod;
  28.     }
  29.     for(int i=bl[l]+1;i<=bl[r]-1;++i) 
  30.         taga[i]+=w,taga[i]%=mod;
  31. }
  32. void Modify_Mul(int l,int r,int w)  {
  33.     reset(bl[l]);
  34.     for(int i=l;i<=min(bl[l]*size,r);++i) a[i]*=w,a[i]%=mod;
  35.     if(bl[l]!=bl[r]) {
  36.         reset(bl[r]);
  37.         for(int i=(bl[r]-1)*size+1;i<=r;++i) 
  38.             a[i]*=w,a[i]%=mod;
  39.     }
  40.     for(int i=bl[l]+1;i<=bl[r]-1;++i) 
  41.         tagm[i]=tagm[i]*w%mod,taga[i]=taga[i]*w%mod;
  42. }
  43. int main() {
  44.     n=read();size=sqrt(n);
  45.     for(int i=1;i<=n;++i)a[i]=read(),tagm[i]=1;tagm[n+1]=1;
  46.     for(int i=1;i<=n;++i)bl[i]=(i-1)/size+1;
  47.     for(int op,aa,b,c,i=1;i<=n;++i) {
  48.         op=read(),aa=read(),b=read(),c=read()%mod;
  49.         if(!op) Modify_Add(aa,b,c);
  50.         else if(op==1)Modify_Mul(aa,b,c);
  51.         else printf("%d\n",(a[b]*tagm[bl[b]]+taga[bl[b]])%mod);
  52.     }
  53.     return 0;
  54. }

数列分块8

  1. #include<cmath>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using std::min;
  6. const int maxn = 100007;
  7. inline int read() {
  8.     int x=0,f=1;
  9.     char c=getchar();
  10.     while(c<'0'||c>'9') {
  11.         if(c=='-')f=-1;
  12.         c=getchar();
  13.     }while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
  14.     return x*f;
  15. }
  16. int n,a[maxn],bl[maxn],tag[maxn],ans=0,size;
  18. void solve(int l,int r,int c) {
  19.     ans=0;
  20.     if(tag[bl[l]]!=-1) {
  21.         for(int i=(bl[l]-1)*size+1;i<=bl[l]*size;++i) 
  22.             a[i]=tag[bl[l]];
  23.         tag[bl[l]]=-1;
  24.         }
  25.     for(int i=l;i<=min(bl[l]*size,r);++i)
  26.     ans+=a[i]==c,a[i]=c;
  27.     //tag[bl[r]]=-1;
  28.     if(bl[l]!=bl[r]) {
  29.         if(tag[bl[r]]!=-1) { 
  30.             for(int i=(bl[r]-1)*size+1;i<=bl[r]*size;++i) 
  31.                 a[i]=tag[bl[r]];
  32.             tag[bl[r]]=-1;
  33.             }
  34.         for(int i=(bl[r]-1)*size+1;i<=r;++i)
  35.             ans+=a[i]==c,a[i]=c;
  36.     }
  37.     for(int i=bl[l]+1;i<=bl[r]-1;++i) {
  38.         if(tag[i]==c)ans+=size;
  39.         else if(tag[i]==-1) {
  40.             for(int j=(i-1)*size+1;j<=i*size;++j) 
  41.                 ans+=a[j]==c,a[j]=c;
  42.             tag[i]=c;
  43.         }
  44.         else tag[i]=c;
  45.     }
  46.     printf("%d\n",ans);
  47. }
  48. int main() {
  49.     n=read();size=sqrt(n);
  50.     memset(tag,-1,sizeof tag);
  51.     for(int i=1;i<=n;++i)a[i]=read();
  52.     for(int i=1;i<=n;++i)bl[i]=(i-1)/size+1;
  53.     for(int aa,b,c,i=1;i<=n;++i) {
  54.         aa=read(),b=read(),c=read();
  55.         solve(aa,b,c);
  56.     }
  57.     return 0;
  58. }

数列分块9

  1. #include<map>
  2. #include<cmath>
  3. #include<vector>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<algorithm>
  7. using std::map;
  8. using std::vector;
  9. inline int read() {
  10.     int x=0,f=1;
  11.     char c=getchar();
  12.     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
  13.     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
  14.     return x*f;
  15. }
  16. const int maxn = 110007;
  17. int v[maxn],val[maxn];
  18. int n,size,bl[maxn],id=0,atmp[671][671],cnt[10086];
  19. vector<int>vec[1007];
  20. map<int,int>mp;
  21. void build(int x) {
  22.     memset(cnt,0,sizeof cnt);
  23.     int mcnt=0,mans=0; 
  24.     for(int i=(x-1)*size+1;i<=n;++i) {
  25.         int vu=v[i]; 
  26.         cnt[vu]++;
  27.         if(mcnt<cnt[vu]||(mcnt==cnt[vu]&&val[vu]<val[mans])) 
  28.             mans=vu,mcnt=cnt[vu];
  29.         atmp[x][bl[i]]=mans;
  30.     }
  31. }
  32. inline int count(int a,int b,int mans) {
  33.     return upper_bound(vec[mans].begin(),vec[mans].end(),b)-lower_bound(vec[mans].begin(),vec[mans].end(),a);
  34. }
  35. int query(int a,int b) {
  36.     int mans=atmp[bl[a]+1][bl[b]-1]; 
  37.     int mcnt=count(a,b,mans);
  38.     for(int i=a;i<=std::min(bl[a]*size,b);++i) {
  39.         int qcnt=count(a,b,v[i]);if(qcnt>mcnt||(qcnt==mcnt&&val[v[i]]<val[mans])) mcnt=qcnt,mans=v[i];
  40.     }
  41.     if(bl[a]!=bl[b]) 
  42.         for(int i=(bl[b]-1)*size;i<=b;++i) {
  43.             int qcnt=count(a,b,v[i]);if(qcnt>mcnt||(qcnt==mcnt&&val[v[i]]<val[mans])) mcnt=qcnt,mans=v[i];
  44.         }
  45.     return val[mans];
  46. }   
  47. int main() {
  48.     n=read();size=sqrt(n);
  49.     for(int i=1;i<=n;++i) {
  50.         v[i]=read();
  51.         if(!mp[v[i]]) 
  52.             mp[v[i]]=++id,val[id]=v[i];
  53.         v[i]=mp[v[i]];
  54.         vec[v[i]].push_back(i);
  55.     }
  56.     for(int i=1;i<=n;++i) bl[i]=(i-1)/size+1;
  57.     for(int i=1;i<=bl[n];++i)build(i);
  58.     for(int a,b,i=1;i<=n;++i) {
  59.         a=read(),b=read();
  60.         if(a>b)std::swap(a,b);
  61.         printf("%d\n",query(a,b));
  62.     }
  63.     return 0;
  64. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注