[JOISC 2021 Day4] 最悪の記者 4 题解

· · 题解

考虑 i 向 a_i 连边，构成一个内向基环树，注意到环上的人的 Rating 都应相等，而树上祖先的 Rating 都比后代小。

假设只有一棵树的情况。注意到这样一个事实：

当确定好不更改哪一些人的 Rating 时，如果这些人的 Rating 满足了他们之间已经有了的限制关系，剩下的人通过更改 Rating 一定能够满足题意。

问题转化成了保留一定数量的点满足限制关系，且这些点的权值和最大，想到树形 DP。

设 f_u 表示第 u 个人必须选，其子树中的选择的点权值和的最大值。

f_u=c_u+\max_{S\in subtree(u)/\{u\}}\sum_{v \in S} f_v

其中 S 是两两没有祖先关系且 Rating 都大于 h_u 的一些点的集合。

发现这些点的选取跟 h_u 有关，把 h_u 离散化后记这些转移式右边那坨为 g_{u,i}，表示仅考虑那些 h_v\geq i 的点的答案。

这样子就 f_u=c_u+g_{u,h_u} 了。

转移 g 数组就把各个儿子对应位置的值相加，再与父亲的 DP 值 [1,h_u] 前缀取 max 即可，线段树合并维护。

现在线段树要支持区间取 max 和合并，也就是说要取 max 还要加，想了很久。

后来问了同机房数据结构神仙才知道要维护两个懒标记，像线段树2一样先 max 后 +，本质上是广义矩阵乘法，写一个 struct 复合懒标记即可。

至于环上的话枚举将值修改成环上的哪一个值或者是全局最小值，取最大值统计答案。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int _=200003;
int n,cnt;
int a[_],h[_],c[_],t[_];
int read(){
    char c=getchar();int x=0;
    while (c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while (c>=48&&c<=57);
    return x;
}
typedef long long ll;
struct tags{ll a,c;tags(ll A=0,ll C=0):a(A),c(C){}};
tags operator*(const tags x,const tags y){
    return tags(max(x.a,y.a-x.c),x.c+y.c); //这里需要稍微推下式子
}
int hd[_],ver[_],nxt[_],tot;
void add(int u,int v){nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;}
tags sg[_<<6];
int lc[_<<6],rc[_<<6];
void pushdown(int p){
    if (sg[p].a||sg[p].c){
        if (!lc[p]) lc[p]=++cnt;
        sg[lc[p]]=sg[lc[p]]*sg[p];
        if (!rc[p]) rc[p]=++cnt;
        sg[rc[p]]=sg[rc[p]]*sg[p];
        sg[p]=tags();
    }
}
ll query(int x,int &p,int l=1,int r=n){
    if (!p) p=++cnt;
    if (l==r) return sg[p].a+sg[p].c;
    pushdown(p);
    int mid=(l+r)>>1;
    if (x<=mid) return query(x,lc[p],l,mid);
    else return query(x,rc[p],mid+1,r);
}
void modify(int x,ll v,int &p,int l=1,int r=n){
    if (!p) p=++cnt;
    if (x>=r) {sg[p]=sg[p]*tags(v,0);return;}
    pushdown(p);
    int mid=(l+r)>>1;
    modify(x,v,lc[p],l,mid);
    if (x>mid) modify(x,v,rc[p],mid+1,r);
}
int merge(int u,int v){
    if (!u||!v) return u^v;
    if (!lc[u]&&!rc[u]) u^=v^=u^=v;
    if (!lc[v]&&!rc[v]) sg[u]=sg[u]*tags(0,sg[v].a+sg[v].c);
    //每一次都pushdown强行新建节点复杂度会爆炸，所以没有儿子节点时改为添加加法懒标记
    else pushdown(u),pushdown(v);
    lc[u]=merge(lc[u],lc[v]);
    rc[u]=merge(rc[u],rc[v]);
    return u;
}
int rt[_];ll buc[_];
bool vis[_],cir[_],tmp[_];
void dfs(int u){
    for (int i=hd[u]; i; i=nxt[i]){
        int v=ver[i];
        if (cir[v]) continue;
        dfs(v);
        rt[u]=merge(rt[u],rt[v]);
    }
    ll v=query(h[u],rt[u])+c[u];
    if (!cir[u]) modify(h[u],v,rt[u]);
}
int main(){
    ll sum=0; n=read();
    for (int i=1; i<=n; ++i){
        a[i]=read(); t[i]=h[i]=read();
        sum+=c[i]=read(); add(a[i],i);
    }
    sort(t+1,t+n+1);
    int rk=unique(t+1,t+n+1)-t-1;
    for (int i=1; i<=n; ++i) h[i]=lower_bound(t+1,t+rk+1,h[i])-t;
    for (int i=1; i<=n; ++i)
        if (!vis[i]){
            int cur=i;
            while (!vis[cur]) tmp[cur]=vis[cur]=1,cur=a[cur];
            if (tmp[cur]) while (!cir[cur]) cir[cur]=1,cur=a[cur];
            cur=i;while (tmp[cur]) tmp[cur]=0,cur=a[cur];
        }
    for (int i=1; i<=n; ++i) if (cir[i]) dfs(i);
    for (int i=1; i<=n; ++i)
        if (cir[i]){
            int cur=i;
            while (cir[cur]){
                cir[cur]=0;
                if (cur^i) rt[i]=merge(rt[i],rt[cur]);
                buc[h[cur]]+=c[cur];
                cur=a[cur];
            }
            ll res=query(1,rt[i]);
            while (!tmp[cur]){
                tmp[cur]=1;
                res=max(res,query(h[cur],rt[i])+buc[h[cur]]);
                cur=a[cur];
            }
            sum-=res;
            while (tmp[cur]){
                tmp[cur]=0;
                buc[h[cur]]=0;
                cur=a[cur];
            }
        }
    printf("%lld\n",sum);
    return 0;
}

时间复杂度 \mathcal{O}(n\log_2n)