当前位置：首页 > news >正文

夏令营Ⅲ期Ⅱ阶段总结

news 2025/10/8 4:50:24

放完假回来。~~头都是晕的~~

Ⅱ阶段就开始上难度了……

树剖+CDQ+整体二分

\(Day\) \(1\)还是讲课，怎么就是树剖力……树剖\(≈dfs*2\)+ 线段树，但\(8.8\)那天我在\(WUT \to TFU\)的航班上写了\(P3372\)，还\(RE\)了，只得了\(40pts\)，到现在仍然没有调出来啊啊啊！！

调不出来没关系，重写就是了。

写了好久，线段树终于出炉。。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll M=1e5+4;
struct Seg{ll sum,laz;
}Tree[M*4];
ll a[M];
void push_up(ll p){Tree[p].sum=Tree[p*2].sum+Tree[p*2+1].sum;
}
void push_down(ll p,ll l,ll r){ll mid=l+(r-l)/2;Tree[p*2].laz+=Tree[p].laz;Tree[p*2+1].laz+=Tree[p].laz;Tree[p*2].sum+=(mid-l+1)*Tree[p].laz;Tree[p*2+1].sum+=(r-mid)*Tree[p].laz;Tree[p].laz=0;
}
void build(ll p,ll l,ll r){if(l==r){Tree[p].sum=a[l];return;}ll mid=l+(r-l)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);push_up(p);
}
void modify(ll p,ll l,ll r,ll ql,ll qr,ll k){if(ql<=l&&r<=qr){Tree[p].laz+=k;Tree[p].sum+=(r-l+1)*k;return;}ll mid=l+(r-l)/2;if(Tree[p].laz)push_down(p,l,r);if(ql<=mid)modify(p*2,l,mid,ql,qr,k);if(qr>mid)modify(p*2+1,mid+1,r,ql,qr,k);push_up(p);
}
ll getsum(ll p,ll l,ll r,ll ql,ll qr){if(ql<=l&&r<=qr)return Tree[p].sum;ll mid=l+(r-l)/2;if(Tree[p].laz)push_down(p,l,r);ll res=0;if(ql<=mid)res+=getsum(p*2,l,mid,ql,qr);if(qr>mid)res+=getsum(p*2+1,mid+1,r,ql,qr);return res;
}
signed main(){ll n,m;cin>>n>>m;for(ll i=1;i<=n;i++)cin>>a[i];build(1,1,n);for(ll i=1;i<=m;i++){ll op,x,y,k;cin>>op>>x>>y;if(op==1){cin>>k;modify(1,1,n,x,y,k);}else cout<<getsum(1,1,n,x,y)<<endl;}return 0;
}

还有树剖板子！

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int M=200005;
struct Seg{ll sum,laz;
}Tree[M*4];
ll a[M];
int cnt=0,res=0,nxt[M],head[M],to[M],fa[M],siz[M],son[M],tp[M],dep[M],dfn[M],rk[M];
ll n,m,r,p;
void add(int u,int v){nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v;
}
void dfs1(int u){siz[u]=1;son[u]=0;for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa[u])continue;fa[v]=u;dep[v]=dep[u]+1;dfs1(v);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}
}
void dfs2(int u,int rt){dfn[u]=++res;rk[res]=u;tp[u]=rt;if(son[u])dfs2(son[u],rt);for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa[u]||v==son[u])continue;dfs2(v,v);}
}
void push_up(int p){Tree[p].sum=Tree[p*2].sum+Tree[p*2+1].sum;
}
void push_down(int p,int l,int r){if(!Tree[p].laz)return;int mid=(l+r)>>1;Tree[p*2].laz+=Tree[p].laz;Tree[p*2+1].laz+=Tree[p].laz;Tree[p*2].sum+=(ll)(mid-l+1)*Tree[p].laz;Tree[p*2+1].sum+=(ll)(r-mid)*Tree[p].laz;Tree[p].laz=0;
}
void build(int p,int l,int r){if(l==r){Tree[p].sum=a[l];return;}int mid=(l+r)>>1;build(p*2,l,mid);build(p*2+1,mid+1,r);push_up(p);
}
void modify(int p,int l,int r,int ql,int qr,ll k){if(ql<=l&&r<=qr){Tree[p].laz+=k;Tree[p].sum+=(ll)(r-l+1)*k;return;}push_down(p,l,r);int mid=(l+r)>>1;if(ql<=mid)modify(p*2,l,mid,ql,qr,k);if(qr>mid)modify(p*2+1,mid+1,r,ql,qr,k);push_up(p);
}
ll query(int p,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return Tree[p].sum;push_down(p,l,r);int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query(p*2,l,mid,ql,qr);if(qr>mid)ans+=query(p*2+1,mid+1,r,ql,qr);return ans;
}
void link_modify(int u,int v,ll val){while(tp[u]!=tp[v]){if(dep[tp[u]]<dep[tp[v]])swap(u,v);modify(1,1,n,dfn[tp[u]],dfn[u],val);u=fa[tp[u]];}if(dep[u]>dep[v])swap(u,v);modify(1,1,n,dfn[u],dfn[v],val);
}
ll link_query(int u,int v){ll ans=0;while(tp[u]!=tp[v]){if(dep[tp[u]]<dep[tp[v]])swap(u,v);ans=(ans+query(1,1,n,dfn[tp[u]],dfn[u]))%p;u=fa[tp[u]];}if(dep[u]>dep[v])swap(u,v);ans=(ans+query(1,1,n,dfn[u],dfn[v]))%p;ans=(ans+p)%p;return ans;
}
int main(){cin>>n>>m>>r>>p;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){int x,y;cin>>x>>y;add(x,y);add(y,x);}dep[r]=0;fa[r]=0;dfs1(r);res=0;dfs2(r,r);vector<ll>b(n+1);for(int i=1;i<=n;i++)b[dfn[i]]=a[i];for(int i=1;i<=n;i++)a[i]=b[i];build(1,1,n);while(m--){int op,x,y;ll z;cin>>op>>x;if(op==1){cin>>y>>z;link_modify(x,y,z);}else if(op==2){cin>>y;cout<<link_query(x,y)<<'\n';}else if(op==3){cin>>z;modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,z);}else if(op==4){ll tmp=query(1,1,n,dfn[x],dfn[x]+siz[x]-1);tmp=(tmp%p+p)%p;cout<<tmp<<'\n';}}return 0;
}

那一天还讲了\(CDQ\)分治+整体二分，~~我连二分答案都写不全还学什么整体二分~~……浅浅粘一下介绍

整体二分

在信息学竞赛中，有一部分题目可以使用二分的办法来解决。但是当这种题目有多次询问且我们每次查询都直接二分可能导致 TLE 时，就会用到整体二分。整体二分的主体思路就是把多个查询一起解决。（所以这是一个离线算法）

可以使用整体二分解决的题目需要满足以下性质：

1.询问的答案具有可二分性

2.修改对判定答案的贡献互相独立，修改之间互不影响效果

3.修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值

4.贡献满足交换律，结合律，具有可加性

5.题目允许使用离线算法

CDQ 分治

CDQ 分治最经典的应用就是处理一些点对 \((i,j)(i≤j)\)，此时它的主要思想如下：

把序列从 mid 切开，分成两半；

把点对分成三类：

第一类是 \(j≤mid\)，即都在左半部分；

第二类是 \(i>mid\)，即都在右半部分；

最后一类是横跨 mid 的部分。

左右两半分别递归，处理前两类点对。

想办法处理最后一类点对。

有点像线段树。。

可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。

普通DP

\(Day2+3+5\)学了\(DP\)，总结一下：

问题	转移方程	注意
LIS	\(f[i]=\max_{j \in[0,i),a_j<a_i}(f[j]+1)\)	\(f[0]=0\)
LCS	\(f[i][j]=\) \(\max\begin{cases}f[i-1][j]\\f[i,j-1] \\f[i-1][j-1]+(a_i= b_j)\end{cases}\)	\(f[i][0]=f[0][j]=0\)
编辑距离	\(f[i][j]=\) \(\min\begin{cases}f[i-1][j]\\f[i,j-1] \\f[i-1][j-1]+(a_i\neq b_j)\end{cases}\)	\(f[i][0]=f[0][j]=0\)
01背包	\(f[i]=\max(f[i],f[j-v[i]]+w[i])\)	\(f[i]=-inf(i>1),f[0]=0\)，倒序遍历
完全背包	\(f[i]=\max(f[i],f[j-v[i]]+w[i])\)	\(f[i]=-inf(i>1),f[0]=0\)，正序遍历
最大字段和	\(f[i]=\max(f[i-1,0])+a[i]\)	初始均为0即可
石子合并（朴素）	\(f[l][r]=\min_{k \in [l,r)}(f[l][k]+f[k][r]+\sum_{i=l}^{r} a_i)\)	\(\forall l \in [1,N],f[l][l]=0\)，其余取\(inf\)
没有上司的舞会	\(\begin{cases}f[x][0]=\sum _{s \in son(x)}\max(f[s][0],f[s][1])\\f[x][1]=H[x]+\sum_{s \in son(x)}f[s][0]\end{cases}\)	从\(root\)开始遍历
分组背包	\(f[x,t]=\max_{\sum_{i=1}^p c_i=t-1}(\sum _{i=1}^p{f[y_i,c_i]})+score[x]\)	有些时候如果构成森林，需要加超级源点
换根DP（P3931）	\(dp[i]=min(e[i], \sum _{i \in son(i)}dp[i])\)	dfs求即可
分层图（P1544）	\(f[i][j][k]=\begin{cases}\max(f[i+1][j][k],f[i+1][j+1][k])+a[i][j]\\\max(f[i][j][k],\max(f[i+1][j][k-1],f[i+1][j+1][k-1])+3*a[i][j])\end{cases}\)	答案为\(\max_{i \in k}f[1][1][i]\),注意边界\(f[n][i][0]和f[n][i][1]\)的值

DP优化：

矩阵快速幂优化：

定义：某些 dp 式形如 \((+,*),(min,+)\)，可以用两个矩阵相乘表示，从而加速。

原因：
\(a + \min(b, c) = \min(a + b, a + c)\)

[矩阵快速幂板子]

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
const int M=105;
struct matrix{int n,m;ll s[M][M];matrix(){clean();}void clean(){memset(s,0,sizeof(s));}void print(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<s[i][j]<<" ";}cout<<endl;}}
}a;
long long ss[M];
matrix operator *(matrix a,matrix b){matrix c;if(a.m!=b.n)return c;c.n=a.n,c.m=b.m;for(int j=1;j<=c.m;j++){for(int i=1;i<=c.n;i++)ss[i]=b.s[i][j];for(int i=1;i<=c.n;i++){for(int k=1;k<=a.m;k++)c.s[i][j]=(c.s[i][j]+a.s[i][k]*ss[k]%mod)%mod;}}return c;
}
matrix qp(matrix a,ll b){matrix ans;ans.n=ans.m=a.n;for(int i=1;i<=a.n;i++)for(int j=1;j<=a.n;j++)ans.s[i][j]=(i==j);for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;
}
int main(){int n;ll k;cin>>n>>k;matrix a,ans;a.n=a.m=n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cin>>a.s[i][j];}ans=qp(a,k);ans.print();return 0;
}

单调队列优化

定义：对于一个固定大小的滑动窗口取最值，可以用单调队列。例如维护最大值，每次去掉前面超出范围的，去掉后面比新值还小的，然后加入新值。

[代码示例]

while(!q.empty()&&i-q.front().t>k+1)q.pop_front();
//处理队首
while(!q.empty()&&/*加入条件*/)q.pop_back();
//加入

斜率优化

定义：对于转移式中含\(p_i×q_j\)这样式子的，我们通常将关于\(j\)的项收集在一起（作为\((x,y)\)），关于\(i\)的项收集在一起（作为\((k,b)\)），构成直线\(y=kx+b\)。对于\(i\)，一般需要求的\(f_i\)在\(b\)中，问题就变成了最大/小化截距\(b\)。又因为斜率一定，让直线和凸包相切即可。

个人理解：和单调队列很相似

[Sample(P3195)]

while(h<t&&cmp(qu[h],qu[h+1])<=2*f[i])h++;
dp[i]=dp[qu[h]]+(f[i]-f[qu[h]]-l-1)*(f[i]-f[qu[h]]-l-1); 
while(h<t&&cmp(qu[t],i)<cmp(qu[t-1],qu[t]))t--;
qu[++t]=i;