题解：P10559 [ICPC2024 Xi'an I] The Last Cumulonimbus Cloud

· · 题解

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

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

关键是，如何定向，能使得每个点的出边个数尽量均匀？我们考虑对每一条边 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;
}