【Codeforces 643D】Bearish Fanpages

mrsrz 1月 20, 2020

set，线段树，模拟。

题目大意：

给定一张 $n$ 个点 $n$ 条边的有向图，每个点有父亲 $fa_i$。保证 $i\neq fa_i$ 且 $i\neq fa_{fa_i}$。

每个点有值 $B_i$。

定义一个结点的度数为 $D_i$，其值等于它的入度加出度加一。定义一个结点的稠密度 $E_i=\lfloor\frac{B_i}{D_i}\rfloor$。

对一个点 $i$，其价值为 $B_i-D_i\times E_i+\sum{j}E_j$，$j$ 表示与 $i$ 直接相连的点（包括入和出）加上 $i$ 本身。

有三个操作：

给定 $x,v$，令 $fa_x=v$。$fa$ 仍满足原来的条件。
给定 $x$，求点 $x$ 的价值。
求所有点中，最小的价值和最大的价值。

题解：

我们考虑对每个结点，维护它所有儿子的信息。

维护 $T_i$ 表示 $\sum_{fa_j=i} E_j$。有 $B_i,E_i,T_i,fa_i$ 这些信息，可以 $O(1)$ 计算一个点的价值。

考虑对每个结点，用一个 multiset 维护其所有儿子的价值，再用一个全局数据结构维护全局最大、最小值。这里可以方便地使用线段树。

考虑一次修改操作，会改变哪些东西：

由于 $fa_x$ 和 $v$ 的度数改变，$fa_x$ 和 $v$ 的儿子的价值会整体加上一个值。
由于 $E_{fa_x},E_{v}$ 改变，$fa_{fa_x},fa_v$ 的价值、multiset 以及 $fa_{fa_{fa_x}},fa_{fa_v}$ 的multiset 改变。
由于 $fa_x$ 和 $v$ 的连边改变，$T_{fa_x},T_{v},T_{fa_{fa_x}},T_{fa_v}$ 改变。

除了第一种情况，只有常数个变量的值需要改变，暴力模拟这个变化过程并更新即可。对于第一种情况，我们对每个 multiset 记一个整体增加量即可。

注意更新的时候先消去原有价值的贡献，再修改 $E,T$，再加上新的价值的贡献。

对于更改过的 multiset，重新把其最大、最小值放入线段树中即可。

另外两个操作都可以 $O(1)$。

时间复杂度 $O((n+q)\log n)$。

Code：

#include<cstdio>
#include<set>
#include<utility>
#include<algorithm>
#define deg(i)(G[i].size()+2)
using namespace std;
const int N=1e5+6;
typedef long long LL; 
namespace sgt{
    pair<LL,LL>d[N<<2];
    void modify(int l,int r,int o,const int&pos,const pair<LL,LL>&val){
        if(l==r)d[o]=val;else{
            const int mid=l+r>>1;
            if(pos<=mid)modify(l,mid,o<<1,pos,val);else modify(mid+1,r,o<<1|1,pos,val);
            d[o]=make_pair(min(d[o<<1].first,d[o<<1|1].first),max(d[o<<1].second,d[o<<1|1].second));
        }
    }
}
int n,m,fa[N];
set<int>G[N];
LL E[N],B[N],sumE[N];
inline LL calc(int i){return B[i]-deg(i)*E[i]+sumE[i]+E[fa[i]]+E[i];}
struct data{
    set<int>st;
    multiset<LL>d;
    LL delta;
    inline void insert(int x){
        if(!st.count(x))st.insert(x),d.insert(calc(x)-delta);
    }
    inline pair<LL,LL>get(){
        return d.empty()?make_pair(0x3f3f3f3f3f3f3f3f,-0x3f3f3f3f3f3f3f3f):
            make_pair(*d.begin()+delta,*d.rbegin()+delta);
    }
    inline void erase(int x){
        if(st.count(x))st.erase(x),d.erase(d.find(calc(x)-delta));
    }
    inline void add(LL x){delta+=x;}
}A[N];
inline void update(int i){sgt::modify(1,n,1,i,A[i].get());}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%lld",B+i);
    for(int i=1;i<=n;++i){
        scanf("%d",fa+i);
        G[fa[i]].insert(i);
    }
    for(int i=1;i<=n;++i)E[i]=B[i]/deg(i),sumE[fa[i]]+=E[i];
    for(int i=1;i<=n;++i)A[fa[i]].insert(i);
    for(int i=1;i<=n;++i)update(i);
    while(m--){
        int op;
        scanf("%d",&op);
        switch(op){
            case 1:{
                int x,v;
                scanf("%d%d",&x,&v);
                int k=fa[x];
                A[fa[fa[k]]].erase(fa[k]);
                A[fa[fa[v]]].erase(fa[v]);
                A[fa[k]].erase(k);
                A[fa[v]].erase(v);
                A[k].erase(x);
                sumE[fa[v]]-=E[v];sumE[fa[k]]-=E[k];
                sumE[k]-=E[x];
                G[k].erase(x);
                LL delta=B[k]/deg(k)-E[k];
                A[k].add(delta);
                G[v].insert(x);
                delta=B[v]/deg(v)-E[v];
                A[v].add(delta);
                E[k]=B[k]/deg(k),E[v]=B[v]/deg(v);
                fa[x]=v;
                sumE[fa[k]]+=E[k];
                sumE[v]+=E[x];
                sumE[fa[v]]+=E[v];
                A[fa[fa[v]]].insert(fa[v]);A[v].insert(x);A[fa[v]].insert(v);
                A[fa[fa[k]]].insert(fa[k]);A[fa[k]].insert(k);
                update(x),update(v),update(k),update(fa[v]),update(fa[k]),update(fa[fa[v]]),update(fa[fa[k]]);
                break;
            }
            case 2:{
                int x;
                scanf("%d",&x);
                printf("%lld\n",calc(x));
                break;
            }
            case 3:{
                printf("%lld %lld\n",sgt::d[1].first,sgt::d[1].second);
                break;
            }
        }
    }
    return 0;
}