L-WeChat Walk

每個大點記錄一下鄰接點的最大步數(shù)

每次修改的時候，枚舉修改點的鄰接的大點來更新

修改大點的時候直接判是不是比鄰接點都大

---

代碼抄的std好不容易才看懂~

Code1

#include<bits/stdc++.h> using namespace std; template <class T=int> T rd() {T res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; } const int N=200010; vector<int> d[N],g[N]; // d原圖 g大點 int n,m,q,Bs; int id[N],cnt; int a[N]; int chmp[N],mx[N]; int h[550][20010]; int ne[N<<4],e[N<<4],idx; int ans[N]; void add(int u) {for(int v:g[u]){int s=id[v];e[idx]=u,ne[idx]=h[s][a[u]],h[s][a[u]]=idx++;;} } int main() {n=rd(),m=rd(),q=rd();Bs=2*sqrt(m)+1;memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int u=rd(),v=rd();d[u].push_back(v);d[v].push_back(u);}// 一個點周圍的大點for(int i=1;i<=n;i++) for(int v:d[i]) if(d[v].size()>=Bs) g[i].push_back(v);for(int i=1;i<=n;i++) if(d[i].size()>=Bs) id[i]=++cnt;// 大點編號for(int i=1;i<=q;i++){int u=rd(),w=rd(); a[u]+=w;if(chmp[u]) {add(u);for(int v:g[u]) mx[v]=max(mx[v],a[u]);continue;}if(!id[u])// 由于a的增加使得周圍某些點冠軍狀態(tài)被破壞 {while(1){int k=0,num=0;for(int v:d[u]){num=max(num,a[v]);if(chmp[v]&&(k==0||a[v]<a[k])) k=v;// 找到步數(shù)最小的冠軍}if(!k)// 周圍已經沒有冠軍 {if(num<a[u]) chmp[u]=i,add(u); // 看看自己是不是冠軍break;}if(a[k]>a[u]) break;// 如果步數(shù)最小的冠軍大于a[u]那么已經不會打破周圍點的冠軍狀態(tài)ans[k]+=i-chmp[k];chmp[k]=0;// 更新周圍點的冠軍狀態(tài) 累計答案}}else{int s=id[u];for(int t=a[u]-w+1;t<=a[u];t++) // a[u]+1~a[u]+w{for(int j=h[s][t];j!=-1;j=ne[j]){int v=e[j];if(a[v]==t&&chmp[v]) ans[v]+=i-chmp[v],chmp[v]=0;}}if(mx[u]<a[u]) chmp[u]=i,add(u);}for(int v:g[u]) mx[v]=max(mx[v],a[u]);}for(int i=1;i<=n;i++) if(chmp[i]) ans[i]+=q-chmp[i];for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0; }

Code2

KeHe大佬題解配合jiangly giegie的代碼
考慮按步數(shù) $w$ 從大到小枚舉

設 $f_u$表示 $u$ 最近一次更新步數(shù)的時刻， ${\text{last}}_u$表示 $u$ 上一次更新步數(shù)的時刻，初值均為最終時刻$q$

若 $u$ 為小點直接暴力算周圍的點。

若 $u$ 為大點，考慮直接維護這個結果（記為 ${\text{mn}}_v$)即每個點步數(shù)更新時，枚舉其周圍所有大點 $v$ 來更新 ${\text{mn}}_v$，由于每個點周圍的大點的個數(shù)不超過$\frac{m}{\text{Bs}}$，復雜度可行

#include<bits/stdc++.h> using namespace std; template <class T=int> T rd() {T res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; } const int N=200010; int n,m,q,Bs; vector<int> e[N],big[N]; int walk[N],mx[N]; int ans[N]; vector<pair<int,int>> event[10005]; int main() {n=rd(),m=rd(),q=rd();Bs=2*sqrt(m)+1;for(int i=1;i<=m;i++){int u=rd(),v=rd();e[u].push_back(v);e[v].push_back(u);}for(int i=1;i<=n;i++) for(int v:e[i]) if(e[v].size()>=Bs) big[i].push_back(v);for(int i=1;i<=q;i++){int u=rd(),w=rd();walk[u]+=w;event[walk[u]].push_back({u,i});}vector<int> f(n+1,q),last(n+1,q),mn(n,q);for(int w=10000;w>=1;w--){for(auto [u,t]:event[w]) {for(auto v:big[u])mn[v]=min(mn[v],t);last[u]=f[u],f[u]=t;}for(auto [u,t]:event[w]){if(e[u].size()<Bs){int r=last[u];for(auto v:e[u]) r=min(r,f[v]);ans[u]+=max(0,r-t);}else{ans[u]+=max(0,min(last[u],mn[u])-t);}}}for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营2 L-WeChat Walk（分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。