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

· · 题解

不考虑题目保证的性质，本题是个经典的图上邻域问题，有众所周知的根号分治 O(q\sqrt m) 做法。

考虑这个做法的本质：给每条边定向，维护每个点 x 所有入边的权值和 s_x，这样修改时只需要修改出边连向的点的 s_y，查询时只需要用 s_x 加上出边连向的点的权值即可。

在本题中，容易证明可以存在一种每次删掉度数不超过 k 的点把图删空的方式（k=10），我们把边按照删除顺序定向，即可让每个点的出边不超过 k 条，复杂度即为 O(n+m+kq)。

更进一步，我们可以离线下来，求出每个点被询问/修改的总次数，每条边定向为这个次数更小的一边，可以证明这个的操作次数是不超过 O(kq) 的，这个做法更好写且常数更小。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
const int M = 3e6+7;
int n,m,q;
int u[M],v[M],sum[N],cnt[N];
int a[N],qc[M],qx[M],qv[M];
vector<int> T[N];
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;
    for(int i=1;i<=m;i++)fin>>u[i]>>v[i];
    for(int i=1;i<=n;i++)fin>>a[i];
    for(int i=1;i<=q;i++)
    {
        fin>>qc[i]>>qx[i];
        if(qc[i]==1)fin>>qv[i];
        cnt[qx[i]]++;
    }
    for(int i=1;i<=m;i++)
    {
        if(cnt[u[i]]>cnt[v[i]])swap(u[i],v[i]);
        T[u[i]].push_back(v[i]);
        sum[v[i]]+=a[u[i]];
    }
    for(int i=1;i<=q;i++)
    {
        int x=qx[i];
        if(qc[i]==1)
        {
            a[x]+=qv[i];
            for(int y:T[x])sum[y]+=qv[i];
        }
        else
        {
            int res=sum[x];
            for(int y:T[x])res+=a[y];
            fout<<res;
            fout.pc('\n');
        }
    }
    return 0;
}