- 区间加法 单点查值
- 把每m个元素分为一块，共有n/m块，每次区间加的操作会涉及O(n/m)个整块，以及区间两侧两个不完整的块中至多2m个元素。
- 我们给每个块设置一个加法标记 atage（记录这个块中元素一起加了多少），每次操作对每个整块直接O(1)标记，而不完整的块由于元素比较少，暴力修改元素的值。每次询问时返回元素的值加上其所在块的加法标记。
- 这样每次操作的复杂度是O(n/m)+O(m)，根据均值不等式，当m取√n时总复杂度最低。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int bl[50010]; //bl[i]代表第 i个数位于哪个块 6 int atag[50010]; //存储每个块内 操作加值的和 7 int block,n,a[50010]; 8 int read(){ 9 int x=0,f=1; 10 char c=getchar(); 11 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} //注意大括号不能省 12 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 13 return x*f; 14 } 15 void add(int l,int r,int c){ 16 for(int i=l;i<=min(bl[l]*block,r);i++) a[i]+=c; //区间覆盖的左半块 17 if(bl[l]!=bl[r]){ //不在同一个块时 18 for(int i=(bl[r]-1)*block+1;i<=r;i++) a[i]+=c; //区间覆盖的右半块 19 } 20 for(int i=bl[l]+1;i<=bl[r]-1;i++) atag[i]+=c; //中间的整块整块处理 21 } 22 int main() 23 { 24 n=read(); 25 block=sqrt(n); //每个块的大小 26 for(int i=1;i<=n;i++) a[i]=read(); 27 for(int i=1;i<=n;i++) bl[i]=(i-1)/block+1; //分块 28 //比如 block=2 那么1 2是属于第一个块的,3 4属于第二个块 这样处理刚好能满足需求 29 for(int i=1;i<=n;i++){ 30 int opt=read(),l=read(),r=read(),c=read(); 31 if(opt==0) add(l,r,c); 32 else printf("%d ",a[r]+atag[bl[r]]); 33 } 34 return 0; 35 }
2. 区间加法 询问区间内小于x的元素个数 (vector 块内排序 lower_bound)
1 #include<cstdio> 2 #include<vector> 3 #include<cmath> 4 #include<algorithm> 5 #define N 50010 6 using namespace std; 7 int a[N],bl[N],atage[N],n,block; 8 vector <int > v[N]; //动态数组 9 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 void reset(int x){ 17 v[x].clear(); //清除x块内元素 18 for(int i=(x-1)*block+1;i<=x*block;i++) v[x].push_back(a[i]); 19 //(x-1)*block+1 表示第 x-1块内的末元素+1,也就是第 x块的第一个元素 20 // x*block 表示 第 x块的末元素 21 sort(v[x].begin(),v[x].end()); 22 } 23 void add(int l,int r,int c){ 24 for(int i=l;i<=min(bl[l]*block,r);i++) a[i]+=c; //最左边的(半)块 25 reset(bl[l]); //a[i]的值改变 容器里的值也要更新 26 if(bl[l]!=bl[r]){ 27 for(int i=(bl[r]-1)*block+1;i<=r;i++) a[i]+=c; //最右边的(半)块 28 reset(bl[r]); 29 } 30 for(int i=bl[l]+1;i<=bl[r]-1;i++) atage[i]+=c; //中间的整块整块处理 31 } 32 void ask(int l,int r,int c){ 33 int sum=0; 34 for(int i=l;i<=min(bl[l]*block,r);i++) if(a[i]+atage[bl[i]]<c) sum++; 35 if(bl[l]!=bl[r]){ 36 for(int i=(bl[r]-1)*block+1;i<=r;i++) if(a[i]+atage[bl[i]]<c) sum++; 37 } 38 for(int i=bl[l]+1;i<=bl[r]-1;i++){ 39 int x=lower_bound(v[i].begin(),v[i].end(),c-atage[i])-v[i].begin(); 40 sum+=x; 41 } 42 printf("%d ",sum); 43 } 44 int main() 45 { 46 n=read(); 47 block=sqrt(n); 48 for(int i=1;i<=n;i++) a[i]=read(); 49 for(int i=1;i<=n;i++){ 50 bl[i]=(i-1)/block+1; 51 v[bl[i]].push_back(a[i]); 52 } 53 for(int i=1;i<=bl[n];i++) sort(v[i].begin(),v[i].end()); //块内排序 54 for(int i=1;i<=n;i++){ 55 int opt=read(),l=read(),r=read(),c=read(); 56 if(opt==0) add(l,r,c); 57 else ask(l,r,c*c); 58 } 59 return 0; 60 }
3. 区间加法 询问区间内小于某个值x的前驱（比其小的最大元素 (set lower_bound)
1 #include<cstdio> 2 #include<algorithm> 3 #include<set> 4 #define N 100010 5 using namespace std; 6 int read(){ 7 int x=0,f=1; char c=getchar(); 8 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 9 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 10 return x*f; 11 } 12 int n,blo; 13 int v[N],bl[N],atag[N]; 14 set <int > st[110]; 15 void add(int l,int r,int c){ 16 for(int i=l;i<=min(r,bl[l]*blo);i++){ 17 st[bl[l]].erase(v[i]); 18 v[i]+=c; 19 st[bl[l]].insert(v[i]); 20 } 21 if(bl[l]!=bl[r]){ 22 for(int i=(bl[r]-1)*blo+1;i<=r;i++){ 23 st[bl[r]].erase(v[i]); 24 v[i]+=c; 25 st[bl[r]].insert(v[i]); 26 } 27 } 28 for(int i=bl[l]+1;i<=bl[r]-1;i++) 29 atag[i]+=c; 30 } 31 int ask(int l,int r,int c){ 32 int ans=-1; 33 for(int i=l;i<=min(r,bl[l]*blo);i++){ 34 int val=v[i]+atag[bl[l]]; 35 if(val<c) ans=max(val,ans); 36 } 37 if(bl[l]!=bl[r]){ 38 for(int i=(bl[r]-1)*blo+1;i<=r;i++){ 39 int val=v[i]+atag[bl[r]]; 40 if(val<c) ans=max(val,ans); 41 } 42 } 43 for(int i=bl[l]+1;i<=bl[r]-1;i++){ 44 int x=c-atag[i]; 45 set <int > ::iterator it=st[i].lower_bound(x); 46 if(it==st[i].begin()) continue; 47 --it; 48 ans=max(ans,*it+atag[i]); 49 } 50 return ans; 51 } 52 int main() 53 { 54 n=read(),blo=1000; 55 for(int i=1;i<=n;i++) v[i]=read(); 56 for(int i=1;i<=n;i++){ 57 bl[i]=(i-1)/blo+1; 58 st[bl[i]].insert(v[i]); 59 } 60 for(int i=1;i<=n;i++){ 61 int opt=read(),a=read(),b=read(),c=read(); 62 if(opt==0) add(a,b,c); 63 else printf("%d ",ask(a,b,c)); 64 } 65 return 0; 66 }
4. 区间加法 区间求和
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define N 50010 5 #define ll long long //真的不开 long long 见祖宗 T^T 6 using namespace std; 7 ll read(){ 8 ll x=0,f=1; char c=getchar(); 9 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 10 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 11 return x*f; 12 } 13 int n,blo,bl[N]; 14 ll a[N],sum[N],atag[N]; // 不能开小 15 void add(int l,int r,int c){ 16 for(int i=l;i<=min(bl[l]*blo,r);i++) 17 a[i]+=c,sum[bl[l]]+=c; 18 if(bl[l]!=bl[r]){ 19 for(int i=(bl[r]-1)*blo+1;i<=r;i++) 20 a[i]+=c,sum[bl[r]]+=c; 21 } 22 for(int i=bl[l]+1;i<=bl[r]-1;i++) 23 atag[i]+=c; 24 } 25 ll ask(int l,int r){ 26 ll ans=0; 27 for(int i=l;i<=min(bl[l]*blo,r);i++) 28 ans+=a[i]+atag[bl[l]]; 29 if(bl[l]!=bl[r]){ 30 for(int i=(bl[r]-1)*blo+1;i<=r;i++) 31 ans+=a[i]+atag[bl[r]]; 32 } 33 for(int i=bl[l]+1;i<=bl[r]-1;i++) 34 ans+=sum[i]+atag[i]*blo; 35 return ans; 36 } 37 int main(){ 38 n=read(),blo=sqrt(n); 39 for(int i=1;i<=n;i++) a[i]=read(); 40 for(int i=1;i<=n;i++){ 41 bl[i]=(i-1)/blo+1; 42 sum[bl[i]]+=a[i]; 43 } 44 for(int i=1;i<=n;i++){ 45 int opt=read(),l=read(),r=read(),c=read(); 46 if(opt==0) add(l,r,c); 47 else printf("%d ",ask(l,r)%(c+1)); 48 } 49 return 0; 50 }
5. 区间求和 区间开方
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define N 50010 5 #define ll long long 6 using namespace std; 7 ll read(){ 8 ll x=0,f=1; char c=getchar(); 9 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 10 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 11 return x*f; 12 } 13 int n,blo; 14 int bl[N],a[N],sum[N],flag[N]; 15 void solve_sqrt(int x){ 16 if(flag[x]) return ; 17 flag[x]=1; 18 sum[x]=0; 19 for(int i=(x-1)*blo+1;i<=x*blo;i++){ 20 a[i]=sqrt(a[i]),sum[x]+=a[i]; 21 if(a[i]>1) flag[x]=0; 22 } 23 } 24 void add(int l,int r,int c){ 25 for(int i=l;i<=min(r,bl[l]*blo);i++){ 26 sum[bl[l]]-=a[i]; 27 a[i]=sqrt(a[i]); 28 sum[bl[l]]+=a[i]; 29 } 30 if(bl[l]!=bl[r]){ 31 for(int i=(bl[r]-1)*blo+1;i<=r;i++){ 32 sum[bl[r]]-=a[i]; 33 a[i]=sqrt(a[i]); 34 sum[bl[r]]+=a[i]; 35 } 36 } 37 for(int i=bl[l]+1;i<=bl[r]-1;i++) 38 solve_sqrt(i); 39 } 40 int ask(int l,int r){ 41 int ans=0; 42 for(int i=l;i<=min(bl[l]*blo,r);i++) 43 ans+=a[i]; 44 if(bl[l]!=bl[r]){ 45 for(int i=(bl[r]-1)*blo+1;i<=r;i++) 46 ans+=a[i]; 47 } 48 for(int i=bl[l]+1;i<=bl[r]-1;i++) 49 ans+=sum[i]; 50 return ans; 51 } 52 int main() 53 { 54 n=read(),blo=sqrt(n); 55 for(int i=1;i<=n;i++){ 56 a[i]=read(); 57 bl[i]=(i-1)/blo+1; 58 sum[bl[i]]+=a[i]; 59 } 60 for(int i=1;i<=n;i++){ 61 int opt=read(),l=read(),r=read(),c=read(); 62 if(opt==0) add(l,r,c); 63 else printf("%d ",ask(l,r)); 64 } 65 return 0; 66 }
6. 单点插入，单点询问
1 #include<cstdio> 2 #include<cmath> 3 #define re register 4 #define in inline 5 #define ll long long 6 #define N 1010 7 using namespace std; 8 in 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>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*f; 13 } 14 15 int n,m,blo; 16 int new_point; //新增点数计数器 17 int a[N][N]; //a[i][j]记录第i块的第j个数 18 int b[N][N]; 19 int len[N]; //len[i]记录第i块的个数 20 21 void rebuild(){ 22 int x=0,t=0; 23 int k=m/blo; //m 新总长 24 if(m%blo!=0) k++; 25 m+=blo; new_point=0; 26 blo=sqrt(m); 27 for(int i=1;i<=k;i++) 28 for(int j=1;j<=len[i];j++){ 29 x++; 30 int bl=(x-1)/blo+1; 31 b[bl][++t]=a[i][j]; 32 if(t>=blo) t=0; 33 } 34 k=m/blo; 35 if(!m%blo) k++; 36 for(int i=1;i<k;i++){ 37 len[i]=blo; 38 for(int j=1;j<=len[i];j++) a[i][j]=b[i][j]; 39 } 40 if(!m%blo) len[k]=blo; 41 else len[k]=m-blo*blo; 42 for(int j=1;j<=len[k];j++) a[k][j]=b[k][j]; 43 } 44 45 int main() 46 { 47 n=read(),m=n; 48 blo=sqrt(n); 49 for(re int i=1;i<=n;i++){ 50 int x=read(),bl=(i-1)/blo+1; 51 a[bl][++len[bl]]=x; 52 } 53 for(re int i=1;i<=n;i++){ 54 int opt=read(),l=read(),r=read(),c=read(); 55 if(!opt){ 56 new_point++; 57 58 int x=0,t; 59 for(t=1;t<=blo;t++){ //暴力找l的位置 60 if(x+len[t]>=l) break; 61 x+=len[t]; 62 } 63 64 len[t]++,l-=x; //暴力插点 65 for(int i=len[t];i>l;i--) a[t][i]=a[t][i-1]; 66 a[t][l]=r; 67 68 if(new_point>=blo) rebuild(); //重新分块 69 } 70 else { 71 re int x=0,t; 72 for(t=1;t<=blo;t++){ 73 if(x+len[t]>=r) break; 74 else x+=len[t]; 75 } 76 printf("%d ",a[t][r-x]); 77 } 78 } 79 return 0; 80 }
7. 区间乘法 区间加法 单点询问
- 乘法优先级高于加法的实现
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define N 100010 5 #define mod 10007 6 #define ll long long 7 using namespace std; 8 ll read(){ 9 ll x=0,f=1; char c=getchar(); 10 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*f; 13 } 14 int n,blo; 15 int a[N],bl[N],atag[N],mtag[N]; 16 void reset(int x){ 17 for(int i=(x-1)*blo+1;i<=min(n,x*blo);i++) //注意与n取min 18 a[i]=(a[i]*mtag[x]+atag[x])%mod; 19 atag[x]=0,mtag[x]=1; 20 } 21 void solve(int opt,int l,int r,int c){ 22 reset(bl[l]); //乘法优先级 23 for(int i=l;i<=min(r,bl[l]*blo);i++){ 24 if(opt==0) a[i]+=c; 25 else a[i]*=c; 26 a[i]%=mod; 27 } 28 if(bl[l]!=bl[r]){ 29 reset(bl[r]); //乘法优先级 30 for(int i=(bl[r]-1)*blo+1;i<=r;i++){ 31 if(opt==0) a[i]+=c; 32 else a[i]*=c; 33 a[i]%=mod; 34 } 35 } 36 for(int i=bl[l]+1;i<=bl[r]-1;i++){ 37 if(opt==0) atag[i]=(atag[i]+c)%mod; 38 else{ 39 atag[i]=(atag[i]*c)%mod; // 注意 40 mtag[i]=(mtag[i]*c)%mod; 41 } 42 } 43 } 44 int main() 45 { 46 n=read(),blo=sqrt(n); 47 for(int i=1;i<=n;i++){ 48 a[i]=read(); 49 bl[i]=(i-1)/blo+1; 50 } 51 for(int i=1;i<=bl[n];i++) mtag[i]=1; //初始化mtag 52 for(int i=1;i<=n;i++){ 53 int opt=read(),l=read(),r=read(),c=read(); 54 if(opt==2) printf("%d ",(a[r]*mtag[bl[r]]+atag[bl[r]])%mod); 55 else solve(opt,l,r,c); 56 } 57 return 0; 58 }
8. 区间询问等于一个数c的元素，并将这个区间的所有元素改为c
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define N 100010 6 #define ll long long 7 using namespace std; 8 ll read(){ 9 ll x=0,f=1; char c=getchar(); 10 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*f; 13 } 14 int n,blo; 15 int a[N],bl[N],tag[N]; 16 void reset(int x){ 17 if(tag[x]==-1) return ; 18 for(int i=(x-1)*blo+1;i<=x*blo;i++) 19 a[i]=tag[x]; 20 tag[x]=-1; 21 } 22 int solve(int l,int r,int c){ 23 int ans=0; 24 reset(bl[l]); 25 for(int i=l;i<=min(r,bl[l]*blo);i++){ 26 if(a[i]!=c) a[i]=c; 27 else ans++; 28 } 29 if(bl[l]!=bl[r]){ 30 reset(bl[r]); 31 for(int i=(bl[r]-1)*blo+1;i<=r;i++) 32 if(a[i]!=c) a[i]=c; 33 else ans++; 34 } 35 for(int i=bl[l]+1;i<=bl[r]-1;i++){ 36 if(tag[i]!=-1){ 37 if(tag[i]==c) ans+=blo; 38 else tag[i]=c; 39 } 40 else{ 41 for(int j=(i-1)*blo+1;j<=i*blo;j++) 42 if(a[j]!=c) a[j]=c; 43 else ans++; 44 tag[i]=c; 45 } 46 } 47 return ans; 48 } 49 int main() 50 { 51 memset(tag,-1,sizeof(tag)); 52 n=read(),blo=sqrt(n); 53 for(int i=1;i<=n;i++){ 54 a[i]=read(); 55 bl[i]=(i-1)/blo+1; 56 } 57 for(int i=1;i<=n;i++){ 58 int l=read(),r=read(),c=read(); 59 printf("%d ",solve(l,r,c)); 60 } 61 return 0; 62 }
9. 区间的最小众数 [ 未AC 88分 ]
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <map> 6 #include <vector> 7 using namespace std; 8 int pos[110000], v[110000], cnt[110000], a[110000]; 9 int id, n, N; 10 int f[510][510]; //块i到j之间的最小众数的id 11 map<int, int> m; //记录每个数的id 12 vector<int> b[51000]; //记录每个数出现的第一个位置 13 void dp(int x) { 14 memset(cnt, 0, sizeof(cnt)); 15 int maxx = 0, ss = 0; //最大的id及最大的值 16 for (int i = (x - 1) * N + 1; i <= n; i++) { 17 int cc = ++cnt[a[i]]; //统计每个数出现的个数 18 if (cc > ss || cc == ss && v[a[i]] < v[maxx]) { 19 ss = cc; 20 maxx = a[i]; 21 } 22 f[x][pos[i]] = maxx; 23 } 24 } 25 int along(int l, int r, int x) // ask how long 26 { 27 int ans = upper_bound(b[x].begin(), b[x].end(), r) - 28 lower_bound(b[x].begin(), b[x].end(), l); //求l到r在x块的长度（r的后继-l的前驱) 29 return ans; 30 } 31 int solve(int x, int y) { 32 int ss = 0, maxx = 0; 33 //完整的块 34 maxx = f[pos[x] + 1][pos[y] - 1]; 35 ss = along(x, y, maxx); 36 //不完整的块 37 for (int i = x; i <= min(pos[x] * N, y); i++) { 38 int cc = along(x, y, a[i]); 39 if (cc > ss || cc == ss && v[a[i]] < v[maxx]) { 40 ss = cc; 41 maxx = a[i]; 42 } 43 } 44 if (pos[x] != pos[y]) { 45 for (int i = (pos[y] - 1) * N + 1; i <= y; i++) { 46 int cc = along(x, y, a[i]); 47 if (cc > ss || cc == ss && v[a[i]] < v[maxx]) { 48 ss = cc; 49 maxx = a[i]; 50 } 51 } 52 } 53 return maxx; 54 } 55 int main() { 56 scanf("%d", &n); 57 N = sqrt(n); 58 for (int i = 1; i <= n; i++) { 59 scanf("%d", &a[i]); 60 pos[i] = (i - 1) / N + 1; 61 if (m[a[i]] == 0) { 62 m[a[i]] = ++id; // a[i]是第几个出现的 63 v[id] = a[i]; 64 } 65 a[i] = m[a[i]]; //强制重新编号 66 b[a[i]].push_back(i); //记录每一个出现的位置 67 } 68 for (int i = 1; i <= pos[n]; i++) dp(i); 69 for (int i = 1; i <= n; i++) { 70 int x, y; 71 scanf("%d%d", &x, &y); 72 if (x > y) 73 swap(x, y); 74 printf("%d ", v[solve(x, y)]); 75 } 76 return 0; 77 }