20240120 A 组模拟赛 题解。
前言
唉，爆零。
这次 T3 居然在谷上和校内 OJ 都是最优解，长度还贼小。
T1
没人看懂题解。
但是赛时有不止一个注意力异常集中的同学注意到了答案是 $(n+2k-1)\cdot \left(\binom{n}{k}-\binom{n}{k-1}\right)$，然后就能 $O(n)$ 做了。
那么是怎么注意到的呢？据某位不愿意透露姓名的在前一天中午单抽出莱伊的同学所说，需要打一个 $O(n^3)$ 暴力。
具体怎么打呢？注意到必定是在某些价格为 $1$ 的位置买入，价格为 $2$ 的地方卖出。那么就是一个括号序列的形式。然后就能 $O(n^3)$ DP 了，具体过程略（这个总不可能不会吧）。
参考代码
结论题要什么代码？
T2
唉。之前看过一道类似但是是最小值版本，这下就不会了。
令每次询问的点为 $a_i,b_i$。
首先考虑 sub3 的部分分，即所有 $a_i$ 相同。那么可以求出每个点与 $a_i$ 的距离作为 $T_2$ 上的点权，然后维护每个点在 $T_2$ 上和 $b_i$ 的带权距离（就是距离加点权）。具体维护方式可以考虑把询问挂在 $T_2$ 上，然后用线段树维护 dfn 序列，具体来说对于一条边权为 $w$ 的边 $u\to v$，容易发现 $v$ 子树内的点与 $v$ 的距离比与 $u$ 的距离小 $w$，其余的要大 $w$，那么区间加即可。
考虑正解怎么写。根据套路，最小距离想点分治，最大距离想直径。
首先容易发现“每个点距离最远的点一定能在直径端点上取到”这个结论在上文所说的带权距离上仍成立，证明略。
那么可以在 $T_1$ 上用之前的方法维护 $T_2$ 点权，然后维护 $T_1$ 的 dfn 线段树中每个区间点集在 $T_2$ 上的最远带权点对，就得到了维护直径的效果。
那么如何维护呢？容易发现 $V_1\cup V_2$ 的最远点对两端点必定是 $V_1$ 或 $V_2$ 的最远点对的端点。证明可以考虑先假设不对，然后在取错的直径上随便取一个点反证法。
复杂度 $O(m\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int t,n,m;
i64 ans[N];
struct edge{
int v,w;
};
vector<edge> e[2][N];
i64 dis1[N],dis2[N];
int dfn[N],sz[N],Tm;
int dfn1[N],mp[N],Tm1;
int ST[20][N];
void dfs1(int x,int fa,i64 dd){
dis1[x]=dd;
dfn1[x]=++Tm1;
mp[dfn1[x]]=x;
sz[x]=1;
for(auto i:e[0][x]){
if(i.v==fa) continue;
dfs1(i.v,x,dd+i.w);
sz[x]+=sz[i.v];
}
}
void dfs2(int x,int fa,i64 dd){
dis2[x]=dd;
dfn[x]=++Tm;
ST[0][dfn[x]]=fa;
for(auto i:e[1][x]){
if(i.v==fa) continue;
dfs2(i.v,x,dd+i.w);
}
}
struct query{
int a,pos;
};
vector<query> q[N];
int lca(int u,int v){
if(u==v) return u;
u=dfn[u];v=dfn[v];
if(u>v) swap(u,v);
++u;
int len=31^__builtin_clz(v-u+1);
return dfn[ST[len][u]]<dfn[ST[len][v-(1<<len)+1]]?ST[len][u]:ST[len][v-(1<<len)+1];
}
i64 dist(int u,int v){
return dis2[u]+dis2[v]-2*dis2[lca(u,v)];
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 mark[N<<2];
pii lnode[N<<2],rnode[N<<2];
void PushUp(int id){
vector<pii> vec;
vec.push_back(lnode[id<<1]);vec.push_back(rnode[id<<1]);
vec.push_back(lnode[id<<1|1]);vec.push_back(rnode[id<<1|1]);
i64 mx=0;
forup(i,0,2){
if(vec[i].fi==-1) continue;
forup(j,i+1,3){
if(vec[j].fi==-1) continue;
i64 dd=dist(vec[i].fi,vec[j].fi)+vec[i].se+vec[j].se;
if(dd>mx){
mx=dd;
lnode[id]=vec[i];rnode[id]=vec[j];
}
}
}
}
void PushDown(int id){
mark[id<<1]+=mark[id];
mark[id<<1|1]+=mark[id];
lnode[id<<1].se+=mark[id];
rnode[id<<1].se+=mark[id];
lnode[id<<1|1].se+=mark[id];
rnode[id<<1|1].se+=mark[id];
mark[id]=0;
}
void Build(int l=1,int r=n,int id=1){
mark[id]=0;
if(l==r){
lnode[id]=mkp(mp[l],dis1[mp[l]]);
rnode[id]=mkp(-1,0);
return;
}
Build(lson);Build(rson);
PushUp(id);
}
void Update(int L,int R,i64 X,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
lnode[id].se+=X;rnode[id].se+=X;
mark[id]+=X;
return;
}
if(mark[id]) PushDown(id);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
i64 Query(int u){
return max(dist(u,lnode[1].fi)+lnode[1].se,dist(u,rnode[1].fi)+rnode[1].se);
}
}mt;
void dfs3(int x,int fa){
for(auto i:q[x]){
ans[i.pos]=mt.Query(i.a);
}
for(auto i:e[0][x]){
int v=i.v,w=i.w;
if(v==fa) continue;
mt.Update(1,n,w);
mt.Update(dfn1[v],dfn1[v]+sz[v]-1,-w*2ll);
dfs3(v,x);
mt.Update(dfn1[v],dfn1[v]+sz[v]-1,w*2ll);
mt.Update(1,n,-w);
}
}
signed main(){
t=read();
n=read();m=read();
forup(k,0,1){
forup(i,1,n-1){
int u=read(),v=read(),w=read();
e[k][u].push_back(edge{v,w});
e[k][v].push_back(edge{u,w});
}
}
forup(i,1,m){
int a=read(),b=read();
q[a].push_back(query{b,i});
}
dfs1(1,0,0);
dfs2(1,0,0);
forup(i,0,18){
forup(j,1,n-(1<<(i+1))+1){
ST[i+1][j]=dfn[ST[i][j]]<dfn[ST[i][j+(1<<i)]]?ST[i][j]:ST[i][j+(1<<i)];
}
}
mt.Build();
dfs3(1,0);
forup(i,1,m){
printf("%lld\n",ans[i]);
}
}
T3
妙题。
首先容易想到一个暴力，即枚举腰的数量，然后对每一对腰找一个底。
注意到对于一对长度为 $l$ 的腰，底的可选区间是 $[1,2l)$，那么让腰尽可能长，底尽可能短显然是不劣的。
所以可以保留最长的 $k$ 对相同长度的边作为腰，然后从小到大双指针找能匹配的底即可。二分 $k$ 能做到 $O(nq\log s)$，其中 $s=\sum c_i$。
注意到对每一对腰匹配一个底是一个二分图匹配的形式，那么可以直接套 Hall 定理了！令 $f(S)$ 为腰集合 $S$ 能连向的底集合的并。由于每个腰能匹配的底都是一个前缀，所以 $f(S)$ 其实就是 $S$ 中最大的那个腰能匹配的前缀。那么可以考虑对每个前缀维护一个 $|f(S)|-|S|$。
具体来说，对于一条长度为 $l$ 的底，视为在 $l$ 处 $+1$，对于一对长度为 $L$ 的腰，视为在 $2L-1$ 处 $-1$，然后维护这个数组的前缀和。容易发现 $P$ 处的前缀和就是一个包含小于 $\frac{P+1}{2}$ 的所有腰的 $S$（显然这样的 $S$ 得到的 $|f(S)|-|S|$ 最有可能小于 $0$）的 $|f(S)|-|S|$。
考虑先假设每一对长度相同的边都作为腰出现。那么在前缀上就有可能有一些负数，所以需要拆掉一些腰。那么设前缀和最小值为 $-x$（注意这里有个负号）。结论是需要拆掉恰好 $\left\lceil\frac{x}{3}\right\rceil$ 对腰。证明考虑由于此处前缀和是 $-x$，那么前面至少有 $x$ 对腰。而每拆一对长度为 $l$ 的腰会使 $l$ 处 $+2$，并且使 $2l-1$ 处 $+1$，即总共 $+3$。那么既然此处都加到非负了，由于它后面的地方均大于等于它，必定也被加到非负了。而前面的可以考虑拆最小的若干对腰，显然也能加到非负。
那么维护一棵单点加，整体求前缀和最小值的线段树即可。具体实现就是对线段树每个结点维护总和和当前结点内前缀和最小值，然后合并就比较简单了，具体见代码。
注意 $2l-1$ 上界是 $2n-1$，线段树要开两倍（因为可能在 $n$ 后面取到最小值）。
复杂度 $O(n\log n)$，我当前不仅是洛谷最优解，还是长度最短解，这就是 zkw 线段树带给我的自信。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
using namespace std;
using i64=long long;
const int N=1<<19,M=2e5+5;
int n,m,c[M];
i64 t;
i64 sum[N<<1],pre[N<<1];//这其实是一棵 zkw 线段树
void Update(int P,int X){
sum[P+N]+=X;pre[P+N]+=X;
for(int i=(P+N)>>1;i;i>>=1){
sum[i]+=X;
pre[i]=min(pre[i<<1],sum[i<<1]+pre[i<<1|1]);
//合并就是 左儿子的最小值 与 左儿子总和加右儿子最小值 取 min
}
}
signed main(){
scanf("%d%d",&n,&m);
forup(i,1,n){
scanf("%d",c+i);
t+=c[i]/2;
Update(i*2-1,-c[i]/2);
if(c[i]&1) Update(i,1);
}
forup(i,1,m){
int l,d;scanf("%d%d",&l,&d);
t+=(c[l]+d)/2-c[l]/2;
Update(l*2-1,c[l]/2-(c[l]+d)/2);
if(d&1) Update(l,(c[l]&1)?-1:1);
c[l]+=d;
printf("%lld\n",t-(pre[1]<0?(abs(pre[1])+2)/3:0));//总的对数减去需要拆掉的对数就是答案
}
}