20240201 A 组模拟赛 题解
前言
芜湖，终于没垫底了。
T1
T2
奇妙的引理。
注意到若一对 $(x,y)$ 中，若存在一个 $k\in(x,y)$ （这是个开区间）满足 $a_k>a_x$ 或 $a_k>a_y$，那么把 $x$ 或 $y$ 换成 $k$ 不仅能选更多的 $z$，单看这两个加起来也变大了。
所以答案的 $x,y$ 必定满足 $\forall k\in (x,y),a_k<a_x \land a_k<a_y$。
容易发现这个开区间 $(x,y)$ 必定是大根笛卡尔树的某子树，数量级是 $O(n)$ 的。
那么就可以直接维护了，把询问挂在左端点上，然后单调栈维护 $y$，再用线段树维护 $z$（就是每次修改形如区间 $ans_i\gets \max(ans_i,a_i+t)$，甚至不用势能分析）。
复杂度 $O(n\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;
#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 n,a[N],m;
i64 ans[N];
struct query{
int r,pos;
};
vector<query> q[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 mx[N<<2],mx2[N<<2],mark[N<<2];
void PushUp(int id){
mx[id]=max(mx[id<<1],mx[id<<1|1]);
}
void Build(int l=1,int r=n,int id=1){
if(l==r){
mx2[id]=a[l];
return;
}
Build(lson);Build(rson);
mx2[id]=max(mx2[id<<1],mx2[id<<1|1]);
}
void PushDown(int id){
auto work=[&](int x){
mx[x]=max(mx[x],mark[id]+mx2[x]);
mark[x]=max(mark[x],mark[id]);
};
work(id<<1);work(id<<1|1);
mark[id]=0;
}
void Update(int L,int R,i64 X,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
mx[id]=max(mx[id],X+mx2[id]);
mark[id]=max(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 L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
return mx[id];
}
if(mark[id]) PushDown(id);
i64 res=0;
if(L<=mid) res=max(res,Query(L,R,lson));
if(mid< R) res=max(res,Query(L,R,rson));
return res;
}
}mt;
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
}
a[n+1]=inf;
m=read();
forup(i,1,m){
int l=read(),r=read();
q[l].push_back(query{r,i});
}
mt.Build();
stack<int> stk;
stk.push(n+1);
fordown(x,n,1){
while(a[x]>a[stk.top()]){
int y=stk.top();stk.pop();
if(y<=n){
int z=y*2-x;
if(z<=n){
mt.Update(z,n,a[x]+a[y]);
}
}
}
int y=stk.top();
if(y<=n){
int z=y*2-x;
if(z<=n){
mt.Update(z,n,a[x]+a[y]);
}
}
stk.push(x);
for(auto i:q[x]){
ans[i.pos]=mt.Query(x,i.r);
}
}
forup(i,1,m){
printf("%lld\n",ans[i]);
}
}
T3
唐。
观察到有个树的部分分，容易发现点分治 $+$ 前缀和优化建图后跑 dijkstra 即可，复杂度 $O(n\log^2 n)$。
由于 $m\le n+50$，那么随便找一棵生成树做前面部分分的优化建图后，最多只剩下 $51$ 条非树边。容易发现若一条路径经过非树边那么必定经过其中一个端点，那么对每条非树边存一个端点假装它们是分治中心然后对整张图跑跟前面部分分差不多的代码即可。复杂度 $O((n\log n+nk)\log(nk))$。
参考代码
#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,int>;
#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=2e5+5;
const i64 inf=1e18;
int n,m,d[N],c[N],cntn;
vector<int> e[N];
vector<pii> oth;
struct edge{int v,w;};
vector<edge> e2[N*75];
i64 dis[N*75];
int vis[N*75];
struct Node{
i64 u,dis;
bool operator <(const Node &r)const{return dis>r.dis;}
};
void dijkstra(){
priority_queue<Node> q;
forup(i,1,cntn){
dis[i]=inf;
}
dis[1]=0;q.push(Node{1,0});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto i:e2[u]){
int v=i.v,w=i.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(Node{v,dis[v]});
}
}
}
}
namespace sub2{
int sz[N],mx[N],als,rt,vis[N];
void dfs1(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs1(i,x);
sz[x]+=sz[i];
mx[x]=max(mx[x],sz[i]);
}
mx[x]=max(mx[x],als-sz[x]);
if(rt==-1||mx[x]<mx[rt]) rt=x;
}
int nd[N],mdis;
vector<pii> sv;
void dfs2(int x,int fa,int dis){
if(!nd[dis]){
nd[dis]=++cntn;
if(dis!=0) e2[nd[dis]].push_back(edge{nd[dis-1],0});
mdis=dis;
}
sv.push_back(mkp(x,dis));
e2[nd[dis]].push_back(edge{x,0});
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs2(i,x,dis+1);
}
}
void dfz(int x,int ps){
dfs2(x,0,0);
for(auto i:sv){
int u=i.fi,dd=i.se;
if(dd<=d[u]){
e2[u].push_back(edge{nd[min(mdis,d[u]-dd)],c[u]});
}
}
sv.clear();
forup(i,0,mdis) nd[i]=0;
mdis=0;
vis[x]=1;
for(auto i:e[x]){
if(vis[i]) continue;
als=(sz[i]<sz[x]?sz[i]:ps-sz[x]);rt=-1;
dfs1(i,x);
dfz(rt,als);
}
}
void solve(){
cntn=n;
als=n;rt=-1;
dfs1(1,0);
dfz(rt,als);
}
}
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int d2[N],nd[N],mdis;
void work(int x){
mem(d2,-1);mem(nd,0);
mdis=0;
queue<int> q;
q.push(x);d2[x]=0;
while(q.size()){
int u=q.front();q.pop();
int dis=d2[u];
if(!nd[dis]){
nd[dis]=++cntn;
if(dis!=0) e2[nd[dis]].push_back(edge{nd[dis-1],0});
mdis=dis;
}
for(auto i:e[u]){
if(~d2[i]) continue;
d2[i]=d2[u]+1;
q.push(i);
}
}
forup(i,1,n){
e2[nd[d2[i]]].push_back(edge{i,0});
if(d[i]>=d2[i]){
e2[i].push_back(edge{nd[min(d[i]-d2[i],mdis)],c[i]});
}
}
}
signed main(){
n=read();m=read();
forup(i,1,n) fa[i]=i;
forup(i,1,m){
int u=read(),v=read();
int fu=getfa(u),fv=getfa(v);
if(fu!=fv){
e[u].push_back(v);
e[v].push_back(u);
fa[fu]=fv;
}else{
oth.push_back(mkp(u,v));
}
}
forup(i,1,n){
d[i]=read();c[i]=read();
}
sub2::solve();
for(auto i:oth){
e[i.fi].push_back(i.se);
e[i.se].push_back(i.fi);
}
for(auto i:oth){
work(i.fi);
}
dijkstra();
forup(i,2,n){
printf("%lld\n",dis[i]);
}
}