题解 | #WeChat Walk#

按每个点有没有超过条边分为重点和轻点.
令超过的为重点,没超过的为轻点.

设数组表示这个点最后成为冠军的时间,初始值为表示还不是冠军.

令数组表示重点附近轻点的最大权值是多少.

令数组为答案数组,用于最后输出.

令数组为下标为多少的为第几个大点,用来缩小空间.

令该点包含的大点下标.

令为小点存在大点的最大值.

对于一次点的修改它分为修改轻点和修改重点.
假如修改轻点,它会对附近的点造成影响,直接访问与它相连的点即可.因为一定不超过条边嘛.
但是如果修改重点的话,因为重点相连的点实在是太多了,因此我们可以直接访问和重点相邻的重点,但是对于和重点相邻的轻点,因为修改的权值不会超过.我们可以通过数值暴力更新其影响.

code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=512;
int Time[N],ma[N],ans[N],id[N],w[N];
vector<int>b,g[N],big[N],sma[N/M][10001];

int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--,y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=0;i<n;i++)
    {
        if(g[i].size()>M)
        {
            id[i]=b.size();
            b.push_back(i);
            for(int j:g[i])
            {
                big[j].push_back(id[i]);
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        if(g[x].size()<=M)
        {
            if(!Time[x])
            {
                int Max=0;
                for(int j:g[x])
                {
                    Max=max(Max,w[j]);
                    if(Time[j]&&w[x]+y>=w[j])
                    {
                        ans[j]+=i-Time[j];
                        Time[j]=0;
                    }
                }
                if(w[x]+y>Max)
                {
                    Time[x]=i;
                }
            }
            for(int j:big[x])
            {
                if(Time[x])    sma[j][w[x]+y].push_back(x);
                ma[j]=max(ma[j],w[x]+y);
            }
        }
        else//假如是大点.
        {
            if(!Time[x])
            {
                int Max=ma[id[x]];
                for(int j:big[x])
                {
                    int v=b[j];
                    Max=max(Max,w[v]);
                    if(Time[v]&&w[x]+y>=w[v])
                    {
                        ans[v]+=i-Time[v];
                        Time[v]=0;
                    }
                }
                if(w[x]+y>Max)
                    Time[x]=i;
                //更新对小点的影响.这里要从大到小更新,因为最新的一次一定是最大的啦~
                for(int j=w[x]+y;j>w[x];j--)
                {
                    for(int v:sma[id[x]][j])
                    {
                        if(Time[v]&&j==w[v])
                        {
                            ans[v]+=i-Time[v];
                            Time[v]=0;
                        }
                    }
                }
            }
        }
        w[x]+=y;
    }
    for(int i=0;i<n;i++)
        if(Time[i])    ans[i]+=q-Time[i];
    for(int i=0;i<n;i++)
        printf("%d\n",ans[i]);
    return 0;
}