按每个点有没有超过条边分为重点和轻点.
令超过的为重点,没超过的为轻点.
设数组表示这个点最后成为冠军的时间,初始值为表示还不是冠军.
令数组表示重点附近轻点的最大权值是多少.
令数组为答案数组,用于最后输出.
令数组为下标为多少的为第几个大点,用来缩小空间.
令该点包含的大点下标.
令为小点存在大点的最大值.
对于一次点的修改它分为修改轻点和修改重点.
假如修改轻点,它会对附近的点造成影响,直接访问与它相连的点即可.因为一定不超过条边嘛.
但是如果修改重点的话,因为重点相连的点实在是太多了,因此我们可以直接访问和重点相邻的重点,但是对于和重点相邻的轻点,因为修改的权值不会超过.我们可以通过数值暴力更新其影响.
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; }