CF643D Bearish Fanpages

题意：

首先，考虑单点询问。
可以发现，每个点的贡献可以求出。
因此，把结果拆成两部分：
一部分是(u)对(f_u，u)的贡献。
一部分是询问(u)时，(f_u)的贡献。
这个容易维护。
再考虑询问最值：可以把问题转化为如下形式
有若干集合，每个集合有一个附加值。
集合中每个元素的实际值是它在集合中的值加上附加值。求所有元素最值。
支持各种修改，添加删除元素。
对每个元素维护一个set，再对每个集合的最值维护set即可。
这道题中，集合(u)就是所有满足(f_x=u)的(x)构成的集合。
代码：

#include <stdio.h>
#include <set>
#define inf 999999999999999999ll
#define ll long long
using namespace std;
int f[100010];ll he[100010],sz[100010];
struct SJd
{
	ll z,i;
	SJd(ll Z,int I)
	{
		z=Z;i=I;
	}
};
bool operator<(const SJd&a,const SJd&b)
{
	if(a.z!=b.z)
		return a.z<b.z;
	return a.i<b.i;
}
ll min(const set<SJd>&se)
{
	if(se.empty())
		return inf;
	return (se.begin())->z;
}
ll max(const set<SJd>&se)
{
	if(se.empty())
		return -inf;
	set<SJd>::iterator it=se.end();
	it--;
	return it->z;
}
set<SJd> se[100010],ai,aa;int K[100010];ll mi[100010],ma[100010],az[100010];
void do_al(int i)
{
	ai.erase(SJd(mi[i],i));
	aa.erase(SJd(ma[i],i));
	mi[i]=min(se[i])+az[i];
	ma[i]=max(se[i])+az[i];
	ai.insert(SJd(mi[i],i));
	aa.insert(SJd(ma[i],i));
}
void cal(int i,int z,bool b=true)
{
	int k=K[i];
	se[f[i]].erase(SJd(he[i],i));
	he[i]+=z*(sz[i]-(sz[i]/k)*(k-1));
	if(b)se[f[i]].insert(SJd(he[i],i));
	do_al(f[i]);
	se[f[f[i]]].erase(SJd(he[f[i]],f[i]));
	he[f[i]]+=z*(sz[i]/k);
	se[f[f[i]]].insert(SJd(he[f[i]],f[i]));
	do_al(f[f[i]]);
	az[i]=sz[i]/k;
	do_al(i);
}
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&sz[i]);
		K[i]=2;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&f[i]);
		K[f[i]]+=1;
	}
	for(int i=1;i<=n;i++)
		cal(i,1);
	for(int i=0;i<q;i++)
	{
		int l;
		scanf("%d",&l);
		if(l==1)
		{
			int x,y,od;
			scanf("%d%d",&x,&y);
			cal(f[x],-1);cal(x,-1,0);cal(y,-1);
			K[f[x]]-=1;K[y]+=1;od=f[x];f[x]=y;
			cal(od,1);cal(x,1);cal(y,1);
		}
		else if(l==2)
		{
			int x;
			scanf("%d",&x);
			printf("%lld
",he[x]+az[f[x]]);
		}
		else
			printf("%lld %lld
",min(ai),max(aa));
	}
	return 0;
}