分块板子（们）：
区间修改，区间求和：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define maxn 50005 #define mod c+1 #define int long long int where[maxn],l[maxn],r[maxn],a[maxn],lazy[maxn],sum[maxn]; int n,c; void update(int L,int R,int w) { int lnum=where[L],rnum=where[R]; if(lnum == rnum) { for(int i = L;i <= R;i++) a[i] += w; sum[lnum] += w * (R - L + 1); return; } for(int i=L;i<=r[lnum];i++) a[i]+=w; for(int i=l[rnum];i<=R;i++) a[i]+=w; sum[lnum]+=w*(r[lnum]-L+1); sum[rnum]+=w*(R-l[rnum]+1); for(int i=lnum+1;i<=rnum-1;i++) lazy[i]+=w; } int query(int L,int R) { int ans=0; int lnum=where[L],rnum=where[R]; if(lnum == rnum) { for(int i = L;i <= R;i++) (ans += a[i] + lazy[lnum]) %= mod; return ans; } for(int i=L;i<=r[lnum];i++) (ans+=a[i])%=mod; for(int i=l[rnum];i<=R;i++) (ans+=a[i])%=mod; (ans+=(r[lnum]-L+1)*lazy[lnum]+(R-l[rnum]+1)*lazy[rnum])%=mod; for(int i=lnum+1;i<=rnum-1;i++) (ans+=sum[i]+lazy[i]*(r[i]-l[i]+1))%=mod; return ans; } main() { scanf("%lld",&n); int tot=0,num=1; for(int i=1;i<=n;i++) { ++tot; if(tot>(int)sqrt(n)) { num++,tot=1; } if(tot==1) l[num]=i; if(tot==(int)sqrt(n)||i==n) r[num]=i; scanf("%lld",&a[i]); where[i]=num; sum[num]+=a[i]; } for(int i=1;i<=n;i++) { int op,L,R; scanf("%lld%lld%lld%lld",&op,&L,&R,&c); if(op==0) update(L,R,c); else printf("%lld ",query(L,R) % mod); } return 0; }
区间开方，区间求和：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<cmath> using namespace std; #define maxn 100005 #define int long long int a[maxn],Max[maxn],where[maxn],l[maxn],r[maxn],sum[maxn]; bool finish[maxn]; int n,m; void update(int L,int R) { int lnum=where[L],rnum=where[R]; if(lnum==rnum) { if(finish[lnum]) return ; int M=0,all=0; for(int i=L;i<=R;i++) { a[i]=(int)sqrt(a[i]); M=max(M,a[i]); all+=a[i]; } for(int i=l[lnum];i<=L-1;i++) { M=max(M,a[i]),all+=a[i];}; for(int j=R+1;j<=r[lnum];j++) { M=max(M,a[j]),all+=a[j];}; if(M==1||M==0) finish[lnum]=1; sum[lnum]=all; return ; } for(int i=lnum+1;i<=rnum-1;i++) { if(finish[i]) continue; int M=0,all=0; for(int j=l[i];j<=r[i];j++) { a[j]=(int)sqrt(a[j]); M=max(M,a[j]); all+=a[j]; } if(M==1||M==0) finish[i]=1; sum[i]=all; } int M=0,all=0; if(!finish[lnum]) { for(int i=l[lnum];i<=r[lnum];i++) { if(i>=L) a[i]=(int)sqrt(a[i]); M=max(M,a[i]); all+=a[i]; } sum[lnum]=all; if(M==0||M==1) finish[lnum]=1; } if(!finish[rnum]) { M=0,all=0; for(int i=l[rnum];i<=r[rnum];i++) { if(i<=R) a[i]=(int)sqrt(a[i]); M=max(M,a[i]); all+=a[i]; } sum[rnum]=all; if(M==0||M==1) finish[rnum]=1; } } int query(int L,int R) { int lnum=where[L],rnum=where[R],M=0; if(lnum==rnum) { if(L==l[lnum]&&R==r[lnum]) return sum[lnum]; for(int i=L;i<=R;i++) M+=a[i]; return M; } for(int i=lnum+1;i<=rnum-1;i++) M+=sum[i]; for(int i=L;i<=r[lnum];i++) M+=a[i]; for(int i=l[rnum];i<=R;i++) M+=a[i]; return M; } main() { scanf("%lld",&n); int tot=0,num=1; for(int i=1;i<=n;i++) { tot++; if(tot>(int)sqrt(n)) { tot=1;num++;} if(tot==1) l[num]=i; if(tot==(int)sqrt(n)||i==n) r[num]=i; scanf("%lld",&a[i]); where[i]=num; sum[num]+=a[i]; } scanf("%lld",&m); for(int i=1;i<=m;i++) { int op,L,R; scanf("%lld%lld%lld",&op,&L,&R); if(op==0) update(min(L,R),max(L,R)); else printf("%lld ",query(min(L,R),max(L,R))); } return 0; }
区间插入，单点询问：
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<vector> #include<algorithm> #include<cmath> using namespace std; #define maxn 100005 vector<int> q[maxn]; int nxt[maxn]; int n,all=1; void rebuild(int num) { int last=nxt[num]; nxt[num]=++all; int sz=q[num].size(); int s=sz/2; for(int i=0;i<sz-s;i++) q[all].push_back(q[num][i+s]); nxt[all] = last; q[num].erase(q[num].begin()+s,q[num].begin()+sz); } void update(int L,int d) { int sum=0,num=0; int i=0; while(1) { if(sum+q[i].size()>=L) { num=i; break; } sum+=q[i].size(); i=nxt[i]; } int p=L-sum; q[num].insert(q[num].begin()+p-1,d); if(q[num].size()>=2*(int)sqrt(n)) rebuild(num); } int query(int R) { int sum=0,num=0; int i=0; while(1) { if(sum+q[i].size()>=R) { num=i; break; } sum+=q[i].size(); i=nxt[i]; } return q[num][R-sum-1]; } int main() { scanf("%d",&n); int tot=0; for(int i=1;i<=n;i++) { tot++; if(tot>(int)sqrt(n)) { tot=1;nxt[all]=all+1;all++; } int x; scanf("%d",&x); q[all].push_back(x); } nxt[0]=1; for(int i=1;i<=n;i++) { int op,L,R,c; scanf("%d%d%d%d",&op,&L,&R,&c); if(op==0) update(L,R); else printf("%d ",query(R)); } return 0; }