文章目录

换教室[[Poetize6] IncDec Sequence](https://www.luogu.com.cn/problem/P4552)[树状数组 3 ：区间修改，区间查询](https://loj.ac/problem/132)[「一本通 4.4 练习 1」Dis](https://loj.ac/problem/10134)[BJOI2018]求和地毯

换教室

简单差分

#include<bits/stdc++.h> using namespace std; #define in Read() int in { int i=0; bool f=true; char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=1e6+5; int n,m,d[N],s[N],t[N]; int ans,dif[N],r[N]; bool check(int mid) { memset(dif,0,sizeof dif); for(int i=1; i<=mid; ++i) { dif[s[i]]+=d[i]; dif[t[i]+1]-=d[i]; } for(int i=1; i<=n; ++i) dif[i]+=dif[i-1]; for(int i=1; i<=n; ++i) if(dif[i]>r[i]) return false; return true; } int main() { n=in,m=in; for(int i=1; i<=n; ++i) r[i]=in; for(int i=1; i<=m; ++i) { d[i]=in; s[i]=in; t[i]=in; } int l=1,r=m; while(l<=r) { int mid=l+r>>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } if(ans==m) puts("0"); else printf("%d\n%d\n",-1,ans+1); return 0; }

[Poetize6] IncDec Sequence

好题！

首先我们在做差分专题，这道题用差分 然后我发现我每次都推到离答案很接近的位置推不下去了

观察发现 第一项为任意数，后面的任意一项都为0的差分数组为所求 可以由$[2,n]$的数字与$diff[1]$配对，或者$[2,n]$的数字自己消耗得到

这个观察不完善，继续观察 发现将数组写到无限项，只有$diff[1]$与$diff[n+1]$非零 并且$diff[1]+diff[n+1]=0$

对于差分数组里的一个正数，可以与负数消耗，也可以与$diff[1]$或$diff[n+1]$消耗 负数同理 容易得到正负数消耗贡献$min(su{m}_{+},su{m}_{-})$ 与头尾消耗贡献$|su{m}_{+/-}|$，并且有$|su{m}_{+}-su{m}_{-}|$进行此此运算 $ans=min(su{m}_{+},su{m}_{-})+|su{m}_{+}-su{m}_{-}|=max(su{m}_{+},su{m}_{-})$

最终得到的数列取决于$|diff[1]|$的种数，发现为$|su{m}_{+}-su{m}_{-}|+1$

#include<bits/stdc++.h> using namespace std; #define in Read() typedef long long ll; ll in{ ll i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=1e5+5; int n; ll a[N],x,y; int main(){ n=in; for(int i=1;i<=n;++i) a[i]=in; for(int i=n;i>=1;--i) a[i]-=a[i-1]; for(int i=2;i<=n;++i){ if(a[i]>0) x+=a[i]; else y-=a[i]; } printf("%lld\n%lld\n",max(x,y),abs(x-y)+1); return 0; }

树状数组 3 ：区间修改，区间查询

树状数组返回前缀和 差分后求树状数组得到原数组 考虑如何求原数组的前缀和

对于数组$\{a_i\}$，它的差分数组为$\{b_i\}$，则$\{a_i\}$的前缀和： $$\sum a_i=\sum \sum _{j=1}^i{b}_j=\sum (n-i+1)b_i=\sum ((n+1)\times b_i-i\times b_i)$$ 前半坨维护一个数组，后半坨维护一个数组

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } #define lowbit(x) (x)&(-x) #define ll long long #define int long long const int N=1e6+5; int n,q; ll b[N],c[N],a[N]; void update(int x,int v){ int p=x; while(p<=n){ b[p]+=v; c[p]+=x*v; p+=lowbit(p); } return; } ll query(int x){ int p=x; ll res=0; while(p>0){ res+=(x+1)*b[p]-c[p]; p-=lowbit(p); } return res; } signed main(){ n=in,q=in; for(int i=1;i<=n;++i){ a[i]=in; update(i,a[i]-a[i-1]); } for(int i=1;i<=q;++i){ int type=in-1; if(!type){ int l=in,r=in,x=in; update(l,x); update(r+1,-x); }else{ int l=in,r=in; printf("%lld\n",query(r)-query(l-1)); } } return 0; }

第一次WA掉了 居然是long long的锅

「一本通 4.4 练习 1」Dis

简单树上差分

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=4e4+5; int n,m; int tot,first[N],nxt[N],aim[N],wei[N]; int f[N][25],deg[N],dis[N]; void ljb(int u,int v,int w){ ++tot; nxt[tot]=first[u]; first[u]=tot; aim[tot]=v; wei[tot]=w; return; } void DFS(int u,int fa){ deg[u]=deg[fa]+1; for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(v==fa) continue; f[v][0]=u; dis[v]=dis[u]+wei[e]; DFS(v,u); } return; } int lca(int u,int v){ if(deg[u]<deg[v]) swap(u,v); for(int i=20;i>=0;--i) if(deg[f[u][i]]>=deg[v]) u=f[u][i]; if(u==v) return u; for(int i=20;i>=0;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; } int main(){ n=in,m=in; for(int i=1;i<n;++i){ int u=in,v=in,w=in; ljb(u,v,w); ljb(v,u,w); } DFS(1,0); for(int l=1;l<=20;++l) for(int u=1;u<=n;++u) f[u][l]=f[f[u][l-1]][l-1]; for(int i=1;i<=m;++i){ int u=in,v=in; printf("%d\n",dis[u]+dis[v]-(dis[lca(u,v)]<<1)); } return 0; }

[BJOI2018]求和

以前做过？ 树剖做的（刷树上差分的题总是发现以前有用树剖做过的，树剖大法好啊） 当时90pts，刚才开了个O2过了 （虽然5个hack数据没过去）

突然想明白：树上差分就是优化的树剖 树剖可以处理的问题比较广，但是$O({\log }^{2}n)$（LCA+线段树） 但是树上差分$O(\log n\times 1)$（LCA+差分）

long long又出锅 注意998244353*2>sizeof(long long)

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=3e5+5,mod=998244353; int n,m,val[N][60],f[N][25]; vector<int>G[N]; int deg[N]; int qpw(int a,int b){ int res=1; while(b){ if(b&1) res=1ll*res*a%mod; a=1ll*a*a%mod; b>>=1; } return res; } void DFS(int u,int fa){ deg[u]=deg[fa]+1; f[u][0]=fa; for(int v:G[u]){ if(v==fa) continue; DFS(v,u); } return; } void get(int u,int fa){ for(int i=1;i<=50;++i) (val[u][i]+=val[fa][i])%=mod; for(int v:G[u]){ if(v==fa) continue; get(v,u); } return; } int lca(int u,int v){ if(deg[u]<deg[v]) swap(u,v); for(int l=20;l>=0;--l) if(deg[f[u][l]]>=deg[v]) u=f[u][l]; if(u==v) return u; for(int l=20;l>=0;--l) if(f[u][l]!=f[v][l]) u=f[u][l],v=f[v][l]; return f[u][0]; } int main(){ n=in; for(int i=1;i<n;++i){ int u=in,v=in; G[u].push_back(v); G[v].push_back(u); } DFS(1,0); for(int i=1;i<=n;++i) val[i][1]=--deg[i]; for(int l=1;l<=20;++l) for(int u=1;u<=n;++u) f[u][l]=f[f[u][l-1]][l-1]; for(int u=1;u<=n;++u) if(val[u][1]) for(int k=1;k<=50;++k) val[u][k]=qpw(val[u][1],k); get(1,0); m=in; for(int i=1;i<=m;++i){ int u=in,v=in,k=in,s=lca(u,v); printf("%d\n",(val[u][k]+val[v][k]+2ll*mod-val[s][k]-val[f[s][0]][k])%mod); } return 0; }

地毯

简单二维差分 说实话二维差分推推柿子、维护一些东西就出来了，以前一直想不明白，现在想不明白以前为什么想不明白

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=1e3+5; int s[N][N],n,m; int main(){ n=in,m=in; for(int i=1;i<=m;++i){ int a=in,b=in,c=in,d=in; ++s[a][b]; --s[a][d+1]; --s[c+1][b]; ++s[c+1][d+1]; } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) printf("%d ",s[i][j]); puts(""); } return 0; }