阿狸的基环内向树森林

Background

当阿狸醒来的时候，发现自己处在基环内向森林的深处，阿狸渴望离开这个乌烟瘴气的地方。“明天还有与桃子的约会呢”，阿狸一边走一边说，“可是，这个森林的出口在哪儿呢？”

阿狸走啊走，走啊走，就是找不到出口。不知所措的他，突然听到了一个苍老的声音：“这是一片有魔法的密林，这里的树的形态也会时不时的变化，晃晃你的小脑瓜，是不是感觉有水在流动呢？”

Description

阿狸所在的森林有 N 个节点，编号从 1 到 N。每个节点都连出去恰好一条有向边，设 i 号点连出去的点为 A[i]。同时，阿狸发现，A[i]≠i，而且 A[A[i]]≠i。

每个节点上都有一些糖果，第 i 个节点上的糖果数为 B[i]。阿狸定义一个节点的糖果稠密度为 C[i]，C[i]求法如下：

假设与 i 距离不超过 1 的点有 D[i]个（包括 i 连出去的点、连向 i 的点以及 i 自己），分别是 P[1]、P[2]…P[D[i]]。

设E[i]=⌊B[i]D[i]⌋E[i]=⌊B[i]D[i]⌋，那么C[i]=B[i]−D[i]×E[i]+∑D[i]j=1E[P[j]]C[i]=B[i]−D[i]×E[i]+∑j=1D[i]E[P[j]]

现在阿狸想让你实现一个糖果稠密度分析仪，这个分析仪要支持三种操作：
➢ 1 i j 表示把 A[i]改为 j，保证 j≠i 且 A[j]≠i。
➢ 2 i 表示询问 C[i]的值，即点 i 的糖果稠密度。
➢ 3 表示询问所有节点中最小的 C[i]的值和最大的 C[i]的值。

Input

第一行两个正整数 N 和 Q，表示节点个数和操作个数。
第二行 N 个正整数，第 i 个数表示 B[i]。
第三行 N 个正整数，第 i 个数表示 A[i]。
接下来 Q 行，每行形如 1 i j 或 2 i 或 3 ，表示操作。

Output

有若干行，表示操作 2 和操作 3 的答案。

Sample Input

5 12
10 20 30 40 50
2 3 4 5 2
2 1
2 2
2 3
2 4
2 5
1 4 2
2 1
2 2
2 3
2 4
2 5
3

Sample Output

10
36
28
40
36
9
57
27
28
29
9 57

Data Limitation

对于测试点 1~2，保证 N,Q≤5×103N,Q≤5×103，1、2、3 操作出现次数均在 Q/3 左右。
对于测试点 3~6，保证 N,Q≤3×104N,Q≤3×104，1、2、3 操作出现次数均在 Q/3 左右。
对于测试点 7~8，保证没有 2 操作，1、3 操作出现次数均在 Q/2 左右。
对于测试点 9~10，保证没有 3 操作，1、2 操作出现次数均在 Q/2 左右。
对于测试点 11~12，保证任何时候 A[i]≤5，1、2、3 操作出现次数均在 Q/3 左右。
对于测试点 13~14，保证任何时候 A[i]≤100，1、2、3 操作出现次数均在 Q/3 左右。
对于测试点 15~16，保证 B[i]≤100，1、2、3 操作出现次数均在 Q/3 左右。
对于 100%的数据，保证 3≤N≤105，1≤Q≤105，1≤B[i]≤1012，1≤A[i]≤N3≤N≤105，1≤Q≤105，1≤B[i]≤1012，1≤A[i]≤N。

分析

分析那个糖果稠密度，发现可以拆分成“只与i及其周围点数量有关的式子”+“周围一圈的E”。直觉那个修改操作的变动量很少。

由于要修改A，所以想到把“周围一圈的E”拆分成“连向i的点的E”+“i连到的点的E”，然后大力维护即可。

我们可以把一个节点 i 的糖果稠密度 C[i]分成两部分，第一部分是 A[i]对 C[i]的贡献E[A[i]]，第二部分是剩下的点对 i 的贡献 C[i]-E[A[i]]，设 F[i]=C[i]-E[A[i]]。

对于一个节点 i，我们维护两个信息，一个是 E[i]，另一个是所有连向 i 的点的 F 值所构成的集合（也可以用两个堆来维护），设这个集合为 Son[i]。

对于全局我们维护一个集合 S，S 的构成如下：我们把每个节点 i 的 min(Son[i])+E[i]和 max(Son[i])+E[i]两个值加到集合 S 中。

显然，操作 2 的答案就是 E[A[i]]+F[i]，而操作 3 的答案就是 min(S)和 max(S)。

考虑操作 1 怎么维护，把 A[i]的值改成了 j，这个操作会影响的节点是 i、j、A[i]、A[j]、A[A[i]]、A[A[j]]、A[A[A[i]]]，其中 i 的 A 发生了改变， A[i]和 j 的 D、E、F 和 Son 发生了改变，于是 A[A[i]]和 A[j]的 F 和 Son 也随之改变，于是 A[A[A[i]]]和 A[A[j]]的 Son 也改变了。所以分别对这七个节点维护即可，顺便再维护一下 S，常数超级大。

总复杂度是 O(NlogN)

以上为题解

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

int i,j,k,n,m,q,ch,o,x,y;

int num[N],f[N];

ll t[N],val[N],dev[N],add[N];

multiset <ll> Ans,Son[N];

set <ll>::iterator it;

void rev(int x)

{

    if (Son[x].empty()) return;

    it=Son[x].begin();

    Ans.insert(*it+add[x]);

    it=Son[x].end();it--;

    Ans.insert(*it+add[x]);

}

void del(int x)

{

    if (Son[x].empty()) return;

    it=Son[x].begin();

    Ans.erase(Ans.find(*it+add[x]));

    it=Son[x].end();it--;

    Ans.erase(Ans.find(*it+add[x]));

}

void Rev(int x)

{

    Son[f[x]].insert(val[x]+dev[x]);

}

void Del(int x)

{

    Son[f[x]].erase(Son[f[x]].find(val[x]+dev[x]));

}

int main()

{

    freopen("forest.in","r",stdin);

    freopen("forest.out","w",stdout);

    R(n);R(q);

    for (i=;i<=n;i++) R(t[i]);

    for (i=;i<=n;i++)

    {

        R(f[i]);

        num[f[i]]++;

    }

    for (i=;i<=n;i++)

    {

        add[i]=t[i]/(num[i]+);

        val[i]=t[i]-(num[i]+)*add[i];

        dev[f[i]]+=add[i];

    }

    for (i=;i<=n;i++) Rev(i);

    for (i=;i<=n;i++) rev(i);

    for (i=;i<=q;i++)

    {

        R(o);

        if (o==)

        {

            R(x);R(y);

            if (f[x]==y) continue;

            del(f[x]);del(f[f[x]]);del(f[f[f[x]]]);

            Del(x);Del(f[x]);Del(f[f[x]]);

            dev[f[x]]-=add[x];num[f[x]]--;

            dev[f[f[x]]]-=add[f[x]];

            add[f[x]]=t[f[x]]/(num[f[x]]+);

            val[f[x]]=t[f[x]]-(num[f[x]]+)*add[f[x]];

            dev[f[f[x]]]+=add[f[x]];

            Rev(f[x]);Rev(f[f[x]]);

            rev(f[x]);rev(f[f[x]]);rev(f[f[f[x]]]);

            f[x]=y;

            del(f[x]);del(f[f[x]]);del(f[f[f[x]]]);

            Del(f[x]);Del(f[f[x]]);

            dev[f[x]]+=add[x];num[f[x]]++;

            dev[f[f[x]]]-=add[f[x]];

            add[f[x]]=t[f[x]]/(num[f[x]]+);

            val[f[x]]=t[f[x]]-(num[f[x]]+)*add[f[x]];

            dev[f[f[x]]]+=add[f[x]];

            Rev(x);Rev(f[x]);Rev(f[f[x]]);

            rev(f[x]);rev(f[f[x]]);rev(f[f[f[x]]]);

            continue;

        }

        if (o==)

        {

            R(x);

            Wl(dev[x]+val[x]+add[f[x]]);

            continue;

        }

        it=Ans.begin();

        W(*it);

        it=Ans.end();it--;

        Wl(*it);

    }

}

/*

input

5 12

10 20 30 40 50

2 3 4 5 2

2 1

2 2

2 3

2 4

2 5

1 4 2

2 1

2 2

2 3

2 4

2 5

3

output

10

36

28

40

36

9

57

27

28

29

9 57

*/

巴特西

codeforces643D