纯板子，不知道为什么放在第 4 个。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=5e4+10; int n,S; int a[maxn]; inline int read(){ int x=0;bool fopt=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } int sum[maxn],L[maxn],R[maxn],belong[maxn],siz[maxn],tag[maxn]; inline void Init(){ S=sqrt(n); for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; siz[belong[i]]++; sum[belong[i]]+=a[i]; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; } } void add(int s,int t,int v){ if(belong[s]==belong[t]){ sum[belong[s]]+=(t-s+1)*v; for(int i=s;i<=t;i++) a[i]+=v; }else{ add(s,R[belong[s]],v); add(L[belong[t]],t,v); for(int i=belong[s]+1;i<belong[t];i++){ tag[i]+=v; sum[i]+=siz[i]*v; } } } int query(int s,int t){ int ans=0; if(belong[s]==belong[t]){ ans+=tag[belong[s]]*(t-s+1); for(int i=s;i<=t;i++) ans+=a[i]; }else{ ans+=query(s,R[belong[s]]); ans+=query(L[belong[t]],t); for(int i=belong[s]+1;i<belong[t];i++) ans+=sum[i]; } return ans; } signed main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read(); if(opt==0){ add(l,r,c); }else{ printf("%lld\n",query(l,r)%(c+1)); } } return 0; } 数列分块入门 5区间开方，区间求和。
开始不板子了。开方并不具有合并性，但是我们发现即使暴力开方 \(2^31\)，在开方五次后都接近 \(1\) 了。所以当一个块内的值都小于等于 \(1\) 的时候（因为有向下取整可能出 \(0\)）的时候，开方也没什么意义了。
所以我们只需要新开一个数组标记一下就好了。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=5e4+10; int n,S; int a[maxn]; inline int read(){ int x=0;bool fopt=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } int belong[maxn],sum[maxn],L[maxn],R[maxn]; bool vis[maxn]; inline void Sqrt(int x){ if(vis[x])return; vis[x]=1;sum[x]=0; for(int i=L[x];i<=R[x];i++){ a[i]=sqrt(a[i]); sum[x]+=a[i]; if(a[i]>1)vis[x]=0; } } inline void modify(int l,int r){ if(vis[belong[l]]==0){ for(int i=l;i<=min(R[belong[l]],r);i++){ sum[belong[l]]-=a[i]; a[i]=sqrt(a[i]); sum[belong[l]]+=a[i]; } vis[belong[l]]=1; for(int i=L[belong[l]];i<=R[belong[l]];i++) if(a[i]>1){ vis[belong[l]]=0;break; } } if(belong[l]!=belong[r]&&vis[belong[r]]==0){ for(int i=L[belong[r]];i<=r;i++){ sum[belong[r]]-=a[i]; a[i]=sqrt(a[i]); sum[belong[r]]+=a[i]; } vis[belong[r]]=1; for(int i=L[belong[r]];i<=R[belong[r]];i++) if(a[i]>1){ vis[belong[r]]=0;break; } } for(int i=belong[l]+1;i<belong[r];i++) Sqrt(i);//如果没有全开方完就暴力开方同时更新标记 } int query(int l,int r){ int ans=0; for(int i=l;i<=min(R[belong[l]],r);i++) ans+=a[i]; if(belong[l]!=belong[r]){ for(int i=L[belong[r]];i<=r;i++) ans+=a[i]; } for(int i=belong[l]+1;i<belong[r];i++) ans+=sum[i]; return ans; } signed main(){ n=read();S=sqrt(n); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; sum[belong[i]]+=a[i]; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; } for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read(); if(l>r)swap(l,r); if(opt==0){ modify(l,r); }else{ printf("%lld\n",query(l,r)); } } return 0; }双倍经验
三倍经验
数列分块入门 6单点插入，单点询问。
震惊，vector 水过，然后 TLE 70 分。
个人感觉是 9 道题里细节最多的，也是最暴力的。
网上的各种 vector + lower_bound 并没有看懂。所以我直接定义 \(a[i][j]\) 表示第 \(i\) 个块中第 \(j\) 个数，\(len[i]\) 表示第 \(i\) 个块的数的个数。
修改？直接暴力循环找所在的块，直接把 \(r\) 以后的往后挪（这也太暴力了吧）。
但是特殊构造的数据会导致某一个块长度变特别大，然后复杂度就 GG 了。
所以我们发现某一个块长度太大的时候，新建一个 \(b[i][j]\) 重新分块，然后再把 \(b[i][j]\) 复制到 \(a[i][j]\) 里去。
很黄很暴力