自动搬运

查看原文

来自洛谷，原作者为

	dlhham 年老，体衰，精力差

搬运于2025-08-24 22:59:10，当前版本为作者最后更新于2024-06-06 15:00:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给一个此题能过，且任意情况下都不比根号分治差的做法：

思路跟正解一样，我们给边定向。对于每次修改，我们把这个点的出边的答案更新上这个值，对于每次查询，我们用这个点的答案，加上其所有出边的答案即可。

关键是，如何定向，能使得每个点的出边个数尽量均匀？我们考虑对每一条边 $u,v$，假设其度数分别是 $deg_u,deg_v$， 那么，我们以 $\frac{deg_v}{deg_u+deg_v}$ 的概率让这条边从 $u$ 连向 $v$，反之从 $v$ 连向 $u$， 这样，每个点出边数的期望是 $D_u=\sum_{v}\frac{deg_v}{deg_u+deg_v}$。

#include <bits/stdc++.h>
#define maxn 1000005
#define ll int
#define mod 998244353
using namespace std;
mt19937 rnd(time(NULL)^clock());
ll rad(ll x,ll y){
	return rnd()%(y-x+1)+x;
}
int n,m,q,B;
ll V[maxn],ans[maxn],deg[maxn];
basic_string<int> edge[maxn],da[maxn];
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
       while(!isdigit(ch)){if(ch=='-') f^=1;ch=gc();}
        while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int main()
{
   fin>>n>>m>>q;
	int u,v;
	for (int i=1;i<=m;i++)
	{
	   fin>>u>>v;
	   if (u>v) swap(u,v);
		edge[u]+=v;
		deg[u]++; deg[v]++;
	}
	for (int i=1;i<=n;i++) fin>>V[i];
	for (int i=1;i<=n;i++)
	{
		for (int j:edge[i])
		{
			if (rad(1,deg[i]+deg[j])<=deg[i])//j->i 
			{
				da[j]+=i;
				ans[i]+=V[j];
			}
			else
			{
				da[i]+=j;
				ans[j]+=V[i];
			}
		}
	}
	int opt,x;
	ll y;
	while (q--)
	{
	   fin>>opt>>x;
		if (opt==2)
		{
			ll ret=ans[x];
			for (int j:da[x]) 
			{
				ret+=V[j];
			}
			fout<<ret;
			fout<<'\n';
		}
		else
		{
		   fin>>y;
			for (int j:da[x])
				ans[j]+=y;
			V[x]+=y;
		}
	}
	return 0;
}