題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的序列表示火車站，每個火車站都有兩個屬性 $[u,v]$，表示在站時間。相鄰兩個火車站之間有一個距離，即從第 $i$ 個火車站到第 $i+1$ 個火車站需要花費 $cost[i]$ 個單位的時間。現在需要完成 $m$ 次操作，每次操作分為三種類型：

0,l,r：詢問從第 $l$ 個火車站開始坐車，是否可以依次經過中途的火車站，直到 $r$ 下車

1,i,w：修改 $cost[i]=w$

2,i,p,q：修改 $[u[i],v[i]]$ 為 $[p,q]$

題目分析：官方題解：

官方題解在實現方面已經說得很清楚了，但我還是有點疑惑，設 $a$ 為左區間，$b$ 為右區間，$ans$ 為合并后的區間，為什么合并的代碼是：

if(a.ok&&b.ok&&a.maxu<=b.minv) { ans.ok=true; } else {ans.ok=false; }

而不是：

if(a.ok&&b.ok&&ans.maxu<=ans.minv) {ans.ok=true; } else {ans.ok=false; }

想了大概有小一會吧，終于給想明白了，其實觀察題解給出的方程不難看出，我們需要的是 $u^{\prime }$ 的前綴最大值和 $v^{\prime }$ 進行比較。換句話說，我們想要知道 $l$ 能否到達 $r$，實際上需要用 $max(u^{\prime }[l],u^{\prime }[l+1],...,u^{\prime }[r])$ 去和 $v^{\prime }[r]$ 進行比較，如果在合并后再去比較的話，可能最小的這個 $v^{\prime }$，實際上就變成 $v^{\prime }[x]$ 了，這里的 $x<r$，那么這樣的比較其實是沒有意義的

所以在合并的時候，需要嚴格控制 $u^{\prime }[i]$ 的取值范圍是左區間，同時 $v^{\prime }[i]$ 的取值范圍是右區間，這樣就可以正確的合并了

代碼：

// Problem: Journey among Railway Stations // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11166/J // Memory Limit: 1048576 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; LL u[N],v[N],cost[N],sum[N]; struct Node {int l,r;LL maxu,minv,lazy;bool ok; }tree[N<<2]; void merge(Node &ans,Node a,Node b) {ans.l=a.l,ans.r=b.r;ans.maxu=max(a.maxu,b.maxu);ans.minv=min(a.minv,b.minv);if(a.ok&&b.ok&&a.maxu<=b.minv) {ans.ok=true;} else {ans.ok=false;} } void pushup(int k) {merge(tree[k],tree[k<<1],tree[k<<1|1]); } void change(int k,LL val) {tree[k].lazy+=val;tree[k].maxu+=val;tree[k].minv+=val; } void pushdown(int k) {if(tree[k].lazy) {LL lz=tree[k].lazy;tree[k].lazy=0;change(k<<1,lz);change(k<<1|1,lz);} } void build(int k,int l,int r) {tree[k]={l,r};if(l==r) {tree[k].maxu=u[l]+sum[l];tree[k].minv=v[l]+sum[l];tree[k].ok=true;return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); } void update(int k,int l,int r,int val,int flag) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {if(flag==1) {//change utree[k].maxu+=val;} else if(flag==2) {//change vtree[k].minv+=val;} else if(flag==3) {//change costchange(k,val);}return;}pushdown(k);update(k<<1,l,r,val,flag);update(k<<1|1,l,r,val,flag);pushup(k); } Node query(int k,int l,int r) {if(tree[k].l>=l&&tree[k].r<=r) {return tree[k];}pushdown(k);int mid=(tree[k].l+tree[k].r)>>1;if(r<=mid) {return query(k<<1,l,r);} else if(l>mid) {return query(k<<1|1,l,r);} else {Node ans;merge(ans,query(k<<1,l,r),query(k<<1|1,l,r));return ans;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {int n;read(n);for(int i=1;i<=n;i++) {read(u[i]);}for(int i=1;i<=n;i++) {read(v[i]);}for(int i=1;i<n;i++) {read(cost[i]);}sum[n]=0;for(int i=n-1;i>=1;i--) {sum[i]=cost[i]+sum[i+1];}build(1,1,n);int q;read(q);while(q--) {int op;read(op);if(op==0) {int l,r;read(l),read(r);puts(query(1,l,r).ok?"Yes":"No");} else if(op==1) {int i,w;read(i),read(w);update(1,1,i,w-cost[i],3);cost[i]=w;} else if(op==2) {int i,p,q;read(i),read(p),read(q);update(1,i,i,p-u[i],1);update(1,i,i,q-v[i],2);u[i]=p,v[i]=q;}}}return 0; }

總結

以上是生活随笔為你收集整理的2021牛客多校1 - Journey among Railway Stations(线段树区间合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

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