以前了解过分块，知道就是把数据分成sqrt(N)块来加速更新及查找操作，但是没练习过，今天找到题目练习分块！
这个东西感觉有点优化过的暴力的感觉。
内存限制：256 MiB时间限制：100 ms标准输入输出
题意是对一个整数进行区间+d操作或者询问单点的值，n<=50,000。
n不是很大，分块的复杂度O(N*sqrt(N))可以承受，这个题很简单直接分就好了，对于整块直接加在tag里，否则暴力的更新小区间的a[]。
询问的时候输出tag[i]+a[i]就是答案。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[50050]; 4 int tag[330]; 5 inline int read() 6 { 7 register int s=0,m=0;register char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();} 9 while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); 10 return m?-s:s; 11 } 12 int main(){ 13 int n,m,i,j; 14 int opt,l,r,c,b; 15 while(cin>>n){ 16 m=sqrt(n); 17 memset(tag,0,sizeof(tag)); 18 for(i=1;i<=n;++i) a[i]=read(); 19 for(i=1;i<=n;++i){ 20 opt=read(),l=read(),r=read(),c=read(); 21 if(opt){ 22 printf("%d ",a[r]+tag[(r+m-1)/m]); 23 } 24 else{ 25 int lid=(l+m-1)/m,rid=(r+m-1)/m; 26 for(;l<=r&&l<=lid*m;l++)a[l]+=c; 27 for(;r>=l&&r>=(rid-1)*m+1;r--)a[r]+=c; 28 for(lid++;lid<rid;lid++)tag[lid]+=c; 29 } 30 } 31 } 32 return 0; 33 }
题意:给出一个数列，进行两种操作，一个是区间+d,一个是询问区间[l,r]之内不大于c*c的数的个数。
和上一个的不同在于这个需要块内排序，想到这一点就迎刃而解了，始终保持每个块内的元素都是有序的。区间修改时，对于整块
直接加在tag里面，残缺的部分暴力加在a[i]上，然后对这个块重新排序。询问类似于修改，整块部分直接二分查找，残缺部分暴力枚举。
总的复杂度O(N*log(N)+N*sqrt(N)*log(sqrt(N)))。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 int a[50050],tag[330]; 5 vector<int>g[330]; 6 int tot,n,m; 7 void resort(int u){ 8 g[u].clear(); 9 for(int i=(u-1)*m+1;i<=u*m&&i<=n;++i)g[u].push_back(a[i]); 10 sort(g[u].begin(), g[u].end()); 11 } 12 void add(int l,int r,int c){ 13 int lid=(l+m-1)/m,rid=(r+m-1)/m; 14 for(;l<=lid*m&&l<=r;l++) a[l]+=c;resort(lid); 15 for(;r>=(rid-1)*m+1&&r>=l;--r) a[r]+=c;resort(rid); 16 for(int i=lid+1;i<rid;++i)tag[i]+=c; 17 } 18 void ask(int l,int r,int c){ 19 int ans=0;int lid=(l+m-1)/m,rid=(r+m-1)/m; 20 for(;l<=lid*m&&l<=r;++l) ans+=(a[l]+tag[lid]<c); 21 for(;r>=(rid-1)*m+1&&r>=l;--r) ans+=(a[r]+tag[rid]<c); 22 for(int i=lid+1;i<rid;++i) ans+=lower_bound(g[i].begin(),g[i].end(),c-tag[i])-g[i].begin(); 23 cout<<ans<<endl; 24 } 25 int main(){ 26 int opt,l,r,c,i; 27 while(scanf("%d",&n)!=EOF){ 28 memset(tag,0,sizeof(tag)); 29 m=sqrt(n),tot=n/m+1; 30 for(i=1;i<=tot;++i) g[i].clear(); 31 for(i=1;i<=n;++i) scanf("%d",a+i); 32 for(i=1;i<=tot;++i) resort(i); 33 for(i=1;i<=n;++i){ 34 scanf("%d%d%d%d",&opt,&l,&r,&c); 35 if(opt==0) add(l,r,c); 36 else ask(l,r,c*c); 37 } 38 } 39 return 0; 40 }
#6279. 数列分块入门 3
题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间加法，询问区间内小于某个值 xxx 的前驱（比其小的最大元素）。
和上一题类似，用同样的方法维护一个有序块然后二分查找比对出最大的就好了。当然这里使用set可以更方便，因为有重复元素，
用到了multiset,注意他erase的时候会清除所有val所以使用iterator定位删除较好。
//找了半天bug，因为我原先的写法是for(;l<=r&&l<=f[l]*M;l++)...;错误在于当l跳到下一个块的时候f[l]*M的值也会变化，导致出错。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 const int maxn=333; 6 multiset<int,greater<int> >S[maxn]; 7 multiset<int>::iterator it; 8 int a[100010],f[100010],tag[maxn],N,M; 9 void add(int l,int r,int c){ 10 for(int i=l;i<=f[l]*M&&i<=r;++i){ 11 S[f[l]].erase(S[f[l]].lower_bound(a[i])); 12 a[i]+=c; 13 S[f[l]].insert(a[i]); 14 } 15 if(f[l]!=f[r]){ 16 for(int i=(f[r]-1)*M+1;i<=r;++i){ 17 S[f[r]].erase(S[f[r]].lower_bound(a[i])); 18 a[i]+=c; 19 S[f[r]].insert(a[i]); 20 } 21 } 22 for(int i=f[l]+1;i<=f[r]-1;++i)tag[i]+=c; 23 } 24 void ask(int l,int r,int c){ 25 int ans=-1; 26 for(int i=l;i<=f[l]*M&&i<=r;++i){ 27 if(a[i]+tag[f[l]]<c) ans=max(ans,a[i]+tag[f[l]]); 28 } 29 if(f[l]!=f[r]){ 30 for(int i=(f[r]-1)*M+1;i<=r;++i){ 31 if(a[i]+tag[f[r]]<c) ans=max(ans,a[i]+tag[f[r]]); 32 } 33 } 34 for(int i=f[l]+1;i<=f[r]-1;++i){ 35 it=S[i].upper_bound(c-tag[i]); 36 if(it==S[i].end()) continue; 37 ans=max(ans,*it+tag[i]); 38 } 39 printf("%d ",ans); 40 } 41 int query(int s,int t,int k){ 42 int ans=-1; 43 for(int i=s;i<=min(f[s]*M,t);i++){ 44 int tmp=a[i]+tag[f[s]]; 45 if(tmp<k) ans=max(ans,tmp); 46 } 47 if(f[s]!=f[t]){ 48 for(int i=(f[t]-1)*M+1;i<=t;i++){ 49 int tmp=a[i]+tag[f[t]]; 50 if(tmp<k) ans=max(ans,tmp); 51 } 52 } 53 54 return ans; 55 } 56 int main(){ 57 int i,op,l,r,c; 58 while(scanf("%d",&N)==1){ 59 M=sqrt(N); 60 memset(tag,0,sizeof(tag)); 61 for(i=1;i<=M+1;i++)S[i].clear(); 62 for(i=1;i<=N;++i){ 63 scanf("%d",a+i); 64 f[i]=(i-1)/M+1; 65 S[f[i]].insert(a[i]); 66 } 67 for(i=1;i<=N;++i){ 68 scanf("%d%d%d%d",&op,&l,&r,&c); 69 if(op==0) add(l,r,c); 70 else ask(l,r,c); 71 } 72 } 73 return 0; 74 }
#6280. 数列分块入门 4
题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间加法，区间求和。
这个就和线段树lazy标记很相近了，只不过复杂度稍微高了点，但我感觉代码比线段树好写吧。
//注意会爆long long
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 const int maxn=333; 6 LL a[100010],f[100010],sum[maxn],tag[maxn],N,M; 7 void add(int l,int r,int c){ 8 for(int i=l;i<=r&&i<=f[l]*M;++i) a[i]+=c,sum[f[l]]+=c; 9 if(f[l]!=f[r]) 10 for(int i=r;i>=l&&i>=(f[r]-1)*M+1;--i) a[i]+=c,sum[f[r]]+=c; 11 for(int i=f[l]+1;i<=f[r]-1;++i) tag[i]+=c; 12 } 13 void ask(int l,int r,int c){ 14 LL ans=0; 15 for(int i=l;i<=r&&i<=f[l]*M;++i){ 16 ans+=a[i]+tag[f[l]]; 17 ans%=c; 18 } 19 if(f[r]!=f[l]){ 20 for(int i=r;i>=l&&i>=(f[r]-1)*M+1;--i){ 21 ans+=a[i]+tag[f[r]]; 22 ans%=c; 23 } 24 } 25 for(int i=f[l]+1;i<=f[r]-1;++i){ 26 ans=(ans+sum[i])%c+M%c*tag[i]%c; 27 ans%=c; 28 } 29 cout<<ans<<endl; 30 } 31 int main(){ 32 int i,op,l,r,c; 33 while(scanf("%lld",&N)==1){ 34 M=sqrt(N); 35 memset(tag,0,sizeof(tag)); 36 memset(sum,0,sizeof(sum)); 37 for(i=1;i<=N;++i){ 38 scanf("%lld",a+i); 39 f[i]=(i-1)/M+1; 40 sum[f[i]]+=a[i]; 41 } 42 for(i=1;i<=N;++i){ 43 scanf("%d%d%d%d",&op,&l,&r,&c); 44 if(op==0) add(l,r,c); 45 else ask(l,r,c+1); 46 } 47 } 48 return 0; 49 }
题目描述
给出一个长为 n 的数列 ，以及 n 个操作，操作涉及区间开方，区间求和。
可以证明int范围内的数最多向下取整开方次数不超过五次就会变成1，从而再怎么开结果都不会变，知道这个结论就好办了。
设计一个标记，记录当前块内的数是否全为1，每次操作的时候如果标记是1就不用再次操作了。复杂度O(4*N+N*sqrt(N))=O(N*sqrt(N))。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 const int maxn=333; 6 int a[100010],f[100010],sum[maxn],tag[maxn],N,M; 7 void add(int l,int r,int c){ 8 for(int i=l;i<=r&&i<=f[l]*M;++i){ 9 sum[f[l]]-=a[i]; 10 a[i]=sqrt(a[i]); 11 sum[f[l]]+=a[i]; 12 } 13 if(f[l]!=f[r]){ 14 for(int i=r;i>=l&&i>=(f[r]-1)*M+1;--i){ 15 sum[f[r]]-=a[i]; 16 a[i]=sqrt(a[i]); 17 sum[f[r]]+=a[i]; 18 } 19 } 20 for(int i=f[l]+1;i<=f[r]-1;++i){ 21 if(tag[i]) continue; 22 LL ok=1; 23 for(int j=(i-1)*M+1;j<=i*M;++j){ 24 sum[i]-=a[j]; 25 a[j]=sqrt(a[j]); 26 sum[i]+=a[j]; 27 if(a[j]>1) ok=0; 28 } 29 tag[i]=ok; 30 } 31 } 32 void ask(int l,int r,int c){ 33 LL ans=0; 34 for(int i=l;i<=r&&i<=f[l]*M;++i) ans+=a[i]; 35 if(f[l]!=f[r]){ 36 for(int i=r;i>=l&&i>=(f[r]-1)*M+1;--i) ans+=a[i]; 37 } 38 for(int i=f[l]+1;i<=f[r]-1;++i) ans+=sum[i]; 39 cout<<ans<<endl; 40 } 41 int main(){ 42 int i,op,l,r,c; 43 while(scanf("%d",&N)==1){ 44 M=sqrt(N); 45 memset(tag,0,sizeof(tag)); 46 memset(sum,0,sizeof(sum)); 47 for(i=1;i<=N;++i){ 48 scanf("%d",a+i); 49 f[i]=(i-1)/M+1; 50 sum[f[i]]+=a[i]; 51 } 52 for(i=1;i<=N;++i){ 53 scanf("%d%d%d%d",&op,&l,&r,&c); 54 if(op==0) add(l,r,c); 55 else ask(l,r,c); 56 } 57 } 58 return 0; 59 }
题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及单点插入，单点询问，数据随机生成。
第一行输入一个数字 nnn。
第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。
若 opt=0，表示在第 l个数字前插入数字 r
若 opt=1表示询问 ar的值
由于数据是随机的，所以不用担心被卡，大胆的用vector分块吧。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 #define f(o) (((o-1)/M)+1) 6 const int maxn=333; 7 int N,M; 8 vector<int> v[maxn]; 9 void insert(int l,int x){ 10 for(int i=1;;i++){ 11 if(l<=v[i].size()){ 12 v[i].insert(v[i].begin()+l-1,x); 13 break; 14 } 15 l-=v[i].size(); 16 } 17 } 18 int ask(int r){ 19 for(int i=1;;i++){ 20 if(r<=v[i].size()){ 21 return v[i][r-1]; 22 } 23 r-=v[i].size(); 24 } 25 } 26 int main(){ 27 int i,opt,l,r,c; 28 scanf("%d",&N); 29 M=sqrt(N); 30 for(i=1;i<=N;++i){ 31 scanf("%d",&c); 32 v[f(i)].push_back(c); 33 } 34 for(i=1;i<=N;++i){ 35 scanf("%d%d%d%d",&opt,&l,&r,&c); 36 if(opt==0){ 37 insert(l,r); 38 } 39 else{ 40 printf("%d ",ask(r)); 41 } 42 } 43 return 0; 44 }
题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间乘法，区间加法，单点询问。
在这个oj做题就没1A过，数组越界一直提示WA，找了一下午，最后对了半天把数组开大了就过了，shit。
经典的线段树题目吧，，维护mul和add标记即可，mul优先，暴力更新所有在不完整块所属块内的元素。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 const int maxn=1333; 6 int mod=10007; 7 int N,M,a[111110],f[111110]; 8 int add[maxn],mul[maxn]; 9 void reset(int u){ 10 for(int i=(u-1)*M+1;i<=u*M;++i) 11 a[i]=(a[i]*mul[u]+add[u])%mod; 12 mul[u]=1,add[u]=0; 13 } 14 void _f(int l,int r,int c,bool op){ 15 reset(f[l]); 16 for(int i=l;i<=r&&i<=f[l]*M;++i){ 17 op==0?a[i]+=c:a[i]*=c; 18 a[i]%=mod; 19 } 20 if(f[r]!=f[l]){ 21 reset(f[r]); 22 for(int i=r;i>=l&&i>=(f[r]-1)*M+1;--i){ 23 op==0?a[i]+=c:a[i]*=c; 24 a[i]%=mod; 25 } 26 } 27 for(int i=f[l]+1;i<=f[r]-1;++i){ 28 if(op==0) (add[i]+=c)%=mod; 29 else{ 30 (add[i]*=c)%=mod; 31 (mul[i]*=c)%=mod; 32 } 33 } 34 } 35 void _ask(int r){ 36 cout<<(a[r]*mul[f[r]]+add[f[r]])%mod<<endl;; 37 } 38 int main(){ 39 int i,opt,l,r,c; 40 for(i=1;i<=1000;++i) mul[i]=1; 41 scanf("%d",&N); 42 M=sqrt(N); 43 for(i=1;i<=N;++i){ 44 scanf("%d",a+i); 45 f[i]=(i-1)/M+1; 46 } 47 for(i=1;i<=N;++i){ 48 scanf("%d%d%d%d",&opt,&l,&r,&c); 49 if(opt==0){ 50 _f(l,r,c,opt); 51 } 52 else if(opt==1){ 53 _f(l,r,c,opt); 54 } 55 else{ 56 _ask(r); 57 } 58 } 59 return 0; 60 }
题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。
设计一个标记数组记录当前块内的元素是否都是相同的某个值就好了，注意暴力查询/更改时要先下放标记。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define bg(x) (((x-1)*M)+1) 4 #define ed(x) (x*M) 5 #define inf 0x3f3f3f3f 6 #define LL long long 7 const int maxn=503; 8 int mod=10007; 9 int N,M,a[111110],f[111110]; 10 int tag[maxn]; 11 void reset(int u){ 12 if(tag[u]==-1) return; 13 for(int i=bg(u);i<=ed(u);++i){ 14 a[i]=tag[u]; 15 } 16 tag[u]=-1; 17 } 18 void ask(int l,int r,int c){ 19 int ans=0; 20 reset(f[l]); 21 for(int i=l;i<=r&&i<=ed(f[l]);++i) ans+=(a[i]==c); 22 if(f[r]!=f[l]){ 23 reset(f[r]); 24 for(int i=r;i>=l&&i>=bg(f[r]);--i) ans+=(a[i]==c); 25 } 26 for(int i=f[l]+1;i<=f[r]-1;++i){ 27 if(tag[i]!=-1){ 28 if(tag[i]==c) ans+=M; 29 } 30 else{ 31 for(int j=bg(i);j<=ed(i);++j) ans+=(a[j]==c); 32 } 33 } 34 cout<<ans<<endl; 35 } 36 void solve(int l,int r,int c){ 37 reset(f[l]); 38 for(int i=l;i<=r&&i<=ed(f[l]);++i) a[i]=c; 39 if(f[r]!=f[l]){ 40 reset(f[r]); 41 for(int i=r;i>=l&&i>=bg(f[r]);--i) a[i]=c; 42 } 43 for(int i=f[l]+1;i<=f[r]-1;++i)tag[i]=c; 44 } 45 int main(){ 46 int i,l,r,c; 47 memset(tag,-1,sizeof(tag)); 48 scanf("%d",&N); 49 M=sqrt(N); 50 for(i=1;i<=N;++i){ 51 scanf("%d",a+i); 52 f[i]=(i-1)/M+1; 53 } 54 for(i=1;i<=N;++i){ 55 scanf("%d%d%d",&l,&r,&c); 56 ask(l,r,c); 57 solve(l,r,c); 58 } 59 return 0; 60 }
题目描述
给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及询问区间的最小众数。
还是分块。对于每一个查询的区间[l,r]的众数，有两种情况，一是边上的不完整块内的元素不影响结果，这样的话问题转化为求中间覆盖到的
整块内的众数。而是边上的不完整块内的元素影响到了结果，说明众数是不完整块内的某个元素。
对于情况1，先预处理出来块之间的众数f[i][j]表示第i个块到第j个块之间的众数，复杂度是O(N*sqrt(N))，询问是O(1)。
对于情况2，对每个相同的元素建立一个vector然后把出现的位置下标升序push进去，这样可以二分做差来查找[l,r]内d出现的次数。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define pb push_back 5 #define inf 0x3f3f3f3f 6 #define bg(o) (((o-1)*M)+1) 7 #define ed(o) (o*M) 8 const int maxn=101010; 9 const int maxm=334; 10 int a[maxn],b[maxn],vis[maxn],N,M; 11 int f[maxn],mode[maxm][maxm][2]; 12 vector<int>v[maxn]; 13 int getid(int x){return lower_bound(v[0].begin(),v[0].end(),x)-v[0].begin()+1;} 14 void init(){ 15 for(int i=1;i<=f[N];++i){ 16 memset(vis,0,sizeof(vis)); 17 int minn=0,minv=inf; 18 for(int j=i;j<=f[N];++j){ 19 for(int k=bg(j);k<=ed(j)&&k<=N;++k) 20 { 21 vis[b[k]]++; 22 if((vis[b[k]]==minn&&b[k]<minv) || vis[b[k]]>minn) 23 { 24 minn=vis[b[k]];minv=b[k]; 25 } 26 } 27 mode[i][j][0]=minv; 28 mode[i][j][1]=minn; 29 } 30 } 31 } 32 int prev(int l,int r,int d){ 33 vector<int>::iterator it1=lower_bound(v[d].begin(),v[d].end(),l); 34 vector<int>::iterator it2=upper_bound(v[d].begin(),v[d].end(),r); 35 return it2-it1; 36 } 37 int solve(int l,int r){ 38 int ans1=inf,ans2=0; 39 for(int i=l;i<=r&&i<=ed(f[l]);++i) 40 { 41 int tmp=prev(l,r,b[i]); 42 if(tmp>ans2||(tmp==ans2 && b[i]<ans1)) 43 { 44 ans1=b[i]; 45 ans2=tmp; 46 } 47 } 48 if(f[r]!=f[l]){ 49 for(int i=r;i>=l&&i>=bg(f[r]);--i) 50 { 51 int tmp=prev(l,r,b[i]); 52 if(tmp>ans2||(tmp==ans2 && b[i]<ans1)) 53 { 54 ans1=b[i]; 55 ans2=tmp; 56 } 57 } 58 } 59 if(f[r]-f[l]>1){ 60 int a1=mode[f[l]+1][f[r]-1][0],a2=mode[f[l]+1][f[r]-1][1]; 61 if((ans2==a2&&a1<ans1)||a2>ans2){ 62 ans1=a1; 63 ans2=a2; 64 } 65 } 66 return ans1; 67 } 68 int main(){ 69 scanf("%d",&N); 70 M=sqrt(N); 71 for(int i=1;i<=N;++i){ 72 scanf("%d",a+i); 73 f[i]=(i-1)/M+1; 74 v[0].pb(a[i]); 75 } 76 sort(v[0].begin(),v[0].end()); 77 v[0].erase(unique(v[0].begin(),v[0].end()),v[0].end()); 78 for(int i=1;i<=N;++i) b[i]=getid(a[i]),v[b[i]].pb(i); 79 int l,r; 80 init(); 81 for(int i=1;i<=N;++i){ 82 scanf("%d%d",&l,&r); 83 if(l>r) swap(l,r); 84 printf("%d ",v[0][solve(l,r)-1]); 85 } 86 return 0; 87 }