题解归档 - cf2239E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2239E
• 本地来源：problems/cf2239E/idea.md
• 题目链接：https://codeforces.com/contest/2239/problem/E
• 原始标题：CF2239E - The end of this world,

思路

CF2239E - The end of this world,

pattern

离线动态连通性 + 可撤销并查集。把高度 h 看成时间点。

claim

对固定高度 h：

• low<=h<=w 的边是安全边，走过后高度不变，可以在同一个安全连通块内任意移动。
• h<low<=w 的边是升高入口，走过后高度变为 low。若在高度 low 时这条边所在安全连通块的最大可达点权为 p，则在所有更低高度，这条边的两个端点都可以得到点权候选 p。

令 F(C,h) 表示高度 h 下安全连通块 C 内，从任意点出发、允许后续升高后能到达的最大 val。则

F(C,h)=max(块内顶点 val, 块内端点挂着的所有更高 low 边入口值)。

从高到低处理所有 low/w 坐标即可，因为入口值只从高高度流向低高度。

necessary

答案只需要在某条边的 w 处更新。任意合法非空 walk 的最优初始高度等于路径上的最小 w，设第一条达到该最小值的边为 e。在走到 e 之前不能经过 low>h 的边，否则高度会升高到超过 h，之后无法通过 w=h 的 e。所以起点和 e 在高度 h 的同一个安全连通块里。

sufficient

若高度 h=w_e 时某个安全连通块包含边 e，则块内任意起点都能先沿安全边走到 e，至少走一条边，再接上该块的 F 所代表的最优后续。因此用 h+F(C,h) 更新整个块内顶点是可行的。

代码中用历史并查集合并树记录“更新整个块”的操作：每次可撤销 DSU 真正合并两个块时新建一个合并树节点；在某个高度需要更新当前块答案时，只给当前根节点打 tag。DFS 结束后从大编号节点向孩子传播 tag，原始顶点得到最终答案。

Implementation note: 当前提交版去掉了中间 wl/wr/p 数组；坐标压缩下标在建边时即用即丢，low 叶子处直接用当前 DSU 块最大值向更低高度挂 preadd。这降低一点内存和分支，不改变 rollback 时序。

brute/check

• sample OK
• stress.py OK: 1000 个随机小图，brute 枚举初始高度和状态 (vertex,current_h) BFS。
• 满规模随机烟测：n=m=500000，本机约 2.6 秒。

edge

• m=0 时没有任何 w 事件，所有点保持 -1。
• 允许多条边；线段树分治按边实例处理。
• 分数最大为 1e9+1e9=2e9，int 安全。

代码

来源：problems/cf2239E/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500000;
const int maxk=1000000;
const int maxseg=21000005;
const int maxstk=2000005;
const int maxnode=21500005;
int n,m,tot,ecnt,ucnt,top,tt;
int s[maxn+5],q[maxk+5];
int a[maxn+5],b[maxn+5],w[maxn+5],low[maxn+5];
int ehead[maxk*4+5],uhead[maxk*4+5],lhead[maxk+5],whead[maxk+5];
int eu[maxseg],ev[maxseg],enxt[maxseg],uv[maxseg],uval[maxseg],unxt[maxseg];
int lnxt[maxn+5],wnxt[maxn+5];
int f[maxn+5],sz[maxn+5],mx[maxn+5],root[maxn+5];
int lc[maxnode],rc[maxnode],tag[maxnode];
struct rec{
    int tp,x,y,z,o,r;
}st[maxstk];
int find(int x){
    while(f[x]!=x) x=f[x];
    return x;
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(sz[x]>sz[y]) swap(x,y);
    st[++top]={1,x,y,sz[y],mx[y],root[y]};
    f[x]=y;
    sz[y]+=sz[x];
    if(mx[x]>mx[y]) mx[y]=mx[x];
    tt++;
    lc[tt]=root[x];
    rc[tt]=root[y];
    tag[tt]=-1;
    root[y]=tt;
}
void addmx(int x,int y){
    x=find(x);
    if(y<=mx[x]) return;
    st[++top]={2,x,0,0,mx[x],0};
    mx[x]=y;
}
void rollback(int lim){
    int x,y;
    while(top>lim){
        if(st[top].tp==1){
            x=st[top].x;
            y=st[top].y;
            f[x]=x;
            sz[y]=st[top].z;
            mx[y]=st[top].o;
            root[y]=st[top].r;
        }else{
            x=st[top].x;
            mx[x]=st[top].o;
        }
        top--;
    }
}
void segadd(int rt,int l,int r,int L,int R,int x,int y){
    int mid;
    if(L<=l and r<=R){
        ecnt++;
        eu[ecnt]=x;
        ev[ecnt]=y;
        enxt[ecnt]=ehead[rt];
        ehead[rt]=ecnt;
        return;
    }
    mid=(l+r)>>1;
    if(L<=mid) segadd(rt<<1,l,mid,L,R,x,y);
    if(R>mid) segadd(rt<<1|1,mid+1,r,L,R,x,y);
}
void preadd(int rt,int l,int r,int R,int x,int y){
    int mid;
    if(r<=R){
        ucnt++;
        uv[ucnt]=x;
        uval[ucnt]=y;
        unxt[ucnt]=uhead[rt];
        uhead[rt]=ucnt;
        return;
    }
    mid=(l+r)>>1;
    preadd(rt<<1,l,mid,R,x,y);
    if(R>mid) preadd(rt<<1|1,mid+1,r,R,x,y);
}
void dfs(int rt,int l,int r){
    int i,lim,mid,x,y,cur;
    lim=top;
    for(i=ehead[rt];i;i=enxt[i]) merge(eu[i],ev[i]);
    for(i=uhead[rt];i;i=unxt[i]) addmx(uv[i],uval[i]);
    if(l==r){
        if(l>1){
            for(i=lhead[l];i;i=lnxt[i]){
                x=mx[find(a[i])];
                if(x>s[a[i]]) preadd(1,1,tot,l-1,a[i],x);
                if(x>s[b[i]]) preadd(1,1,tot,l-1,b[i],x);
            }
        }
        for(i=whead[l];i;i=wnxt[i]){
            x=find(a[i]);
            cur=q[l]+mx[x];
            y=root[x];
            if(cur>tag[y]) tag[y]=cur;
        }
    }else{
        mid=(l+r)>>1;
        dfs(rt<<1|1,mid+1,r);
        dfs(rt<<1,l,mid);
    }
    rollback(lim);
}
int main(){
    int T,i,x,y;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++) scanf("%d",&s[i]);
        tot=0;
        for(i=1;i<=m;i++){
            scanf("%d%d%d%d",&a[i],&b[i],&w[i],&low[i]);
            q[++tot]=w[i];
            q[++tot]=low[i];
        }
        sort(q+1,q+1+tot);
        tot=unique(q+1,q+1+tot)-q-1;
        for(i=1;i<=tot*4+4;i++){
            ehead[i]=0;
            uhead[i]=0;
        }
        for(i=1;i<=tot;i++){
            lhead[i]=0;
            whead[i]=0;
        }
        ecnt=ucnt=top=0;
        tt=n;
        for(i=1;i<=n;i++){
            f[i]=root[i]=i;
            sz[i]=1;
            mx[i]=s[i];
            tag[i]=-1;
        }
        for(i=1;i<=m;i++){
            x=lower_bound(q+1,q+1+tot,low[i])-q;
            y=lower_bound(q+1,q+1+tot,w[i])-q;
            segadd(1,1,tot,x,y,a[i],b[i]);
            lnxt[i]=lhead[x];
            lhead[x]=i;
            wnxt[i]=whead[y];
            whead[y]=i;
        }
        if(tot) dfs(1,1,tot);
        for(i=tt;i>n;i--){
            if(tag[i]>tag[lc[i]]) tag[lc[i]]=tag[i];
            if(tag[i]>tag[rc[i]]) tag[rc[i]]=tag[i];
        }
        for(i=1;i<=n;i++){
            if(i>1) printf(" ");
            printf("%d",tag[i]);
        }
        printf("\n");
    }
    return 0;
}