根号分治 P3396 哈希冲突 一眼根号分治，小就暴力，大就预处理，没啥好说的。 代码： #include using namespace std; #define int long long const int N=1.5e5+5; int a[N],dp[1000][1000]; int n,m,x,y; char c; signed main(){ cin>>n>>m; for(int i=1;i>a[i]; for(int i=1;i>c>>x>>y; if(c=='A'){ if(x `#include using namespace std; #define int long long const int N=1.5e5+5; int a[N],dp[1000][1000]; int n,m,x,y; char c; signed main(){ cin>>n>>m; for(int i=1;i>a[i]; for(int i=1;ifor(int j=1;jsqrt(n);j++) dp[j][i%j]+=a[i]; while(m--){ cin>>c>>x>>y; if(c=='A'){ if(xsqrt(n)) coutdp[x][y]"\n"; else{ int ans=0; for(int i=y;ia[i]; cout"\n"; } } else{ for(int i=1;isqrt(n);i++) dp[i][x%i]+=y-a[x]; a[x]=y; } } return 0; } ` P5309 [Ynoi2011] 初始化 分块+根号分治。 大于根号时直接暴力加，小于根号时，计算前后缀同一周期同一位置的加减情况。 查询分两个部分，一个是暴力加的，一个可以用前后缀的信息计算，代码： #include using namespace std; #define int long long const int sz=128,N=2e5+5,md=1e9+7; const int Z=N/sz+2; int n,m,bl,a[N],s[Z],L[Z],R[Z],pr[sz][sz],sf[sz][sz]; #define bel(x)((x-1)/sz+1) inline void upd(int &x){x+=x>>31&md;} int qry(int l,int r){ int bl=bel(l),br=bel(r),res=0; if(bl==br) for(int i=l;i=l;i--) upd(res+=a[i]-md); for(int i=L[br];i>n>>m; bl=bel(n); for(int i=1;i>a[i]; for(int i=1;i>op; if(op==1){ int x,y,z; cin>>x>>y>>z; z-=md; if(x>=sz) for(int i=y;i=y;i--) upd(pr[x][i]+=z); for(int i=1;i>l>>r; int ans=qry(l,r); for(int i=1;i `#include using namespace std; #define int long long const int sz=128,N=2e5+5,md=1e9+7; const int Z=N/sz+2; int n,m,bl,a[N],s[Z],L[Z],R[Z],pr[sz][sz],sf[sz][sz]; #define bel(x)((x-1)/sz+1) inline void upd(int &x){x+=x>>31&md;} int qry(int l,int r){ int bl=bel(l),br=bel(r),res=0; if(bl==br) for(int i=l;ir;i++) upd(res+=a[i]-md); else{ for(int i=R[bl];i>=l;i--) upd(res+=a[i]-md); for(int i=L[br];ir;i++) upd(res+=a[i]-md); for(int i=bl+1;ibr;i++) upd(res+=s[i]-md); } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; bl=bel(n); for(int i=1;ibl;i++) L[i]=R[i-1]+1,R[i]=i*sz; R[bl]=n; for(int i=1;in;i++) cin>>a[i]; for(int i=1;ibl;i++) for(int j=L[i];jR[i];j++) upd(s[i]+=a[j]-md); while(m--){ int op; cin>>op; if(op==1){ int x,y,z; cin>>x>>y>>z; z-=md; if(x>=sz) for(int i=y;in;i+=x) upd(a[i]+=z),upd(s[bel(i)]+=z); else{ for(int i=x;i>=y;i--) upd(pr[x][i]+=z); for(int i=1;iy;i++) upd(sf[x][i]+=z); } } else{ int l,r; cin>>l>>r; int ans=qry(l,r); for(int i=1;isz;i++){ int bl=(l-1)/i+1,br=(r-1)/i+1; if(bl==br) upd(ans+=pr[i][(r-1)%i+1]-md),upd(ans-=pr[i][(l-1)%i]); else ans=(ans+(br-bl-1)*pr[i][i])%md,upd(ans+=pr[i][(r-1)%i+1]-md),upd(ans+=sf[i][(l-1)%i+1]-md); } coutans'\n'; } } return 0; }` P8250 交友问题 用 bitset 维护每个点的邻居，bitset 的计算根号分治一下即可， 代码： #include using namespace std; const int N=2e5+5; int n,m,q; int dig[N]; map> mp; vector g[N]; bitset get(int u){ bitset res; for(int v:g[u]) res[v]=1; return res; } signed main(){ cin>>n>>m>>q; for(int i=1;i>u>>v; g[u].push_back(v); g[v].push_back(u); dig[u]++,dig[v]++; } for(int i=1;i1000) mp[i]=get(i); for(int i=1;i>u>>v; bitset x=(dig[u]>1000?mp[u]:get(u)); bitset y=(dig[v]>1000?mp[v]:get(v)); y[v]=1; cout `#include using namespace std; const int N=2e5+5; int n,m,q; int dig[N]; mapint,bitset> mp; vectorint> g[N]; bitsetN> get(int u){ bitset res; for(int v:g[u]) res[v]=1; return res; } signed main(){ cin>>n>>m>>q; for(int i=1;i int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); dig[u]++,dig[v]++; } for(int i=1;iif(dig[i]>1000) mp[i]=get(i); for(int i=1;i int u,v; cin>>u>>v; bitset x=(dig[u]>1000?mp[u]:get(u)); bitset y=(dig[v]>1000?mp[v]:get(v)); y[v]=1; coutcount()"\n"; } return 0; }` P5901 [IOI 2009] Regions 对于其中一个是点数大于根号的颜色，预处理一下，一个是差分子树加，一个是前缀和单点加。 同样的思路运用到小于根号的在线，用树状数组维护即可。 注意卡常，代码： #include using namespace std; const int N=2e5+5; const int M=425; int n,r,q,idx,sum; int fa[N],h[N],dfn[N],siz[N],big[N],tag[N],a[N],ans1[25005][M+5],ans2[M+5][25005]; vector t[N],c[N]; inline int read(){ int x=0; char ch=getchar_unlocked(); while(ch'9') ch=getchar_unlocked(); while(ch>='0'&&ch0;i-=i&-i) res+=a[i]; return res; } void dfs(int u){ dfn[u]=++idx,siz[u]=1; for(int v:t[u]) dfs(v),siz[u]+=siz[v]; } inline int get(int u,int v){ int res=0,ans=0; for(int x:c[u]) res+=query(dfn[x]+siz[x]-1)-query(dfn[x]-1); for(int x:c[v]) add(dfn[x]); for(int x:c[u]) ans+=query(dfn[x]+siz[x]-1)-query(dfn[x]-1); return ans-res; } signed main(){ n=read(),r=read(),q=read(); h[1]=read(),c[h[1]].push_back(1); for(int i=2;i `#include using namespace std; const int N=2e5+5; const int M=425; int n,r,q,idx,sum; int fa[N],h[N],dfn[N],siz[N],big[N],tag[N],a[N],ans1[25005][M+5],ans2[M+5][25005]; vectorint> t[N],c[N]; inline int read(){ int x=0; char ch=getchar_unlocked(); while(ch'0'||ch>'9') ch=getchar_unlocked(); while(ch>='0'&&ch'9') { x=(x3)+(x1)+(ch^48); ch=getchar_unlocked(); } return x; } inline void put(int x){ if(x0){ putchar_unlocked('-'); x=-x; } if(x==0){ putchar_unlocked('0'); return; } static int st[20]; int top=0; while(x) st[++top]=x%10,x/=10; while(top) putchar_unlocked(st[top--]+'0'); } inline void add(int x){ for(int i=x;ia[i]++; } inline int query(int x){ int res=0; for(int i=x;i>0;i-=i&-i) res+=a[i]; return res; } void dfs(int u){ dfn[u]=++idx,siz[u]=1; for(int v:t[u]) dfs(v),siz[u]+=siz[v]; } inline int get(int u,int v){ int res=0,ans=0; for(int x:c[u]) res+=query(dfn[x]+siz[x]-1)-query(dfn[x]-1); for(int x:c[v]) add(dfn[x]); for(int x:c[u]) ans+=query(dfn[x]+siz[x]-1)-query(dfn[x]-1); return ans-res; } signed main(){ n=read(),r=read(),q=read(); h[1]=read(),c[h[1]].push_back(1); for(int i=2;i fa[i]=read(),h[i]=read(); t[fa[i]].push_back(i); c[h[i]].push_back(i); } dfs(1); for(int i=1;i if(c[i].size()continue; big[i]=++sum; for(int j=1;jtag[j]=0; for(int u:c[i]) tag[dfn[u]]++; for(int j=1;jtag[j]+=tag[j-1]; for(int j=1;jif(h[j]!=i) ans1[h[j]][big[i]]+=tag[dfn[j]+siz[j]-1]-tag[dfn[j]-1]; for(int j=1;jtag[j]=0; for(int u:c[i]) tag[dfn[u]]++,tag[dfn[u]+siz[u]]--; for(int j=1;jtag[j]+=tag[j-1]; for(int j=1;jif(h[j]!=i) ans2[big[i]][h[j]]+=tag[dfn[j]]; } while(q--){ int u,v; u=read(),v=read(); if(big[u]) put(ans2[big[u]][v]); else if(big[v]) put(ans1[u][big[v]]); else put(get(u,v)); putchar_unlocked('\n'); fflush(stdout); } return 0; }`
根号分治
笔记