題意

給定一個序列 a[] 和初始起點 s ，每次從 i 位置跳躍到 j 要滿足 d-k<=abs(a[i]-a[j])<=d+k ，每次詢問給出 k 和目的位置 x ，詢問是否可行。
n,m<=2e5 。

Solution:

從定義想到連邊。那么本題就是求最小生成樹。邊數為 n^2 ，考慮 boruvka 算法。

算法流程：維護若干連通塊，然后對于每個連通塊向其他連出代價最小的邊，迭代上述過程。

算法證明：只需證明連出的邊一定在 MST 樹上。假設不在，那么一定存在一個環滿足當前邊最大，但是當前邊是所有連出去的邊中最小的邊，所以假設不成立。

可以證明，經過一次連邊后，仍然會形成若干連通塊，且連通塊的個數至少減少一半。時間復雜度為 O(mlogn)。

回到本題。顯然我們不會枚舉所有邊，而是用 set 模擬，時間復雜度 O(nlog^2n) 。

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define ll long long #define PII pair<int,int> #define All(a) a.begin(),a.end() #define F(x) abs(a[x]+d-it->first) #define G(x) abs(a[x]-d-it->first) using namespace std; const int mx=2e5+5; int n,m,cnt,a[mx],bl[mx],dp[mx],fa[mx],vis[mx],s,d,k; set<PII> A; vector<PII> g[mx]; vector<int> f[mx]; void dfs(int x,int fa) {for(auto y:g[x]) {if(vis[y.first]) continue; vis[y.first]=1;dp[y.first]=max(dp[x],y.second);dfs(y.first,x);} } int find(int x) {return (fa[x]==x)?x:fa[x]=find(fa[x]); } void unionset(int x,int y) {int u=find(x),v=find(y);if(u!=v) fa[u]=v; } void Boruvka() {for(int i=1;i<=n;i++) bl[i]=i,fa[i]=i; cnt=n;while(cnt>1) {A.clear(); for(int i=1;i<=n;i++) vis[i]=0;for(int i=1;i<=n;i++) A.insert(make_pair(a[i],i));for(int i=1;i<=cnt;i++) f[i].clear();for(int i=1;i<=n;i++) f[bl[i]].push_back(i);for(int i=1;i<=cnt;i++) {for(auto x:f[i]) {A.erase(make_pair(a[x],x));}int u(0),v(0),Min=INF;for(auto x:f[i]) {auto it=A.lower_bound(make_pair(a[x]+d,0));if(it!=A.end() && F(x) < Min) {Min = F(x);u = x; v = it->second;}if(it--!=A.begin() && F(x) < Min) {Min = F(x);u = x; v = it->second;}it=A.lower_bound(make_pair(a[x]-d,0));if(it!=A.end() && G(x) < Min) {Min = G(x);u = x; v = it->second;}if(it--!=A.begin() && G(x) < Min) {Min = G(x);u = x; v = it->second;}}unionset(u,v); g[u].push_back(make_pair(v,Min)),g[v].push_back(make_pair(u,Min));for(auto x:f[i]) {A.insert(make_pair(a[x],x));}}cnt=0;for(int i=1;i<=n;i++) {if(!vis[find(i)]) {vis[find(i)]=++cnt;}bl[i]=vis[find(i)];}} } int main() {scanf("%d%d%d%d",&n,&m,&s,&d);for(int i=1;i<=n;i++) scanf("%d",&a[i]);Boruvka();memset(vis,0,sizeof(vis)),vis[s]=1,dfs(s,0); // for(int i=1;i<=n;i++) { // printf("dp[%d]=%d\n",i,dp[i]); // }for(int i=1;i<=m;i++) {int x; scanf("%d%d",&x,&k);printf("%s\n",(k>=dp[x])?"yes":"no");} }

總結

以上是生活随笔為你收集整理的【题解】CF1550F Jumping Around的全部內容，希望文章能夠幫你解決所遇到的問題。

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