傳送門

題意：
給出兩個長度為$N$的整數(shù)序列$A_1{A}_2...A_N$,$B_1{B}_2...B_N$。有$M$組詢問$(opt,l,r,d)$，令$n=r?l+1$
若$opt=A$：$?i\in [1,n],a_i=A_{l+i?1}+d,b_i=B_{l+i?1}$
若$opt=B$：$?i\in [1,n],a_i=A_{l+i?1},b_i=B_{l+i?1}+d$
求$min(max\{a_1,a_2,...,a_p,b_{p+1},b_{p+2},...,b_n\}|0\le p\le n)$

題解：
記$ma{x}_a=max\{a_1,a_2,...,a_p\}$，隨著$p$的增大，$ma{x}_a$單調(diào)不降。
記$ma{x}_b=max\{b_{p+1},b_{p+2},...,b_n\}$，隨著$p$的增大，$ma{x}_b$單調(diào)不升。
$max(ma{x}_a,ma{x}_b)$一定先不升，再不降，因此最優(yōu)的$p$可以二分得到：
若$p=mid$時，

• $ma{x}_a>ma{x}_b$，那么最優(yōu)的$p$在$[l,mid]$中；
• $ma{x}_a\le ma{x}_b$，那么最優(yōu)的$p$在$[mid+1,r]$中。

可以用線段樹上二分來得到最優(yōu)的$p$。

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pr; #define FR first #define SE second namespace IO{char buf[1000010],*cur=buf+1000010;inline char getc(){(cur==buf+1000010)?fread(cur=buf,1,1000010,stdin):0;return *cur++;}char buff[1000010],*curr=buff;inline void flush(){fwrite(buff,1,curr-buff,stdout);}inline void putc(const char &ch){(curr==buff+1000010)?fwrite(curr=buff,1,1000010,stdout):0;*curr++=ch;}inline void rd(int &x){x=0;char ch=getc();int f=1;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}x*=f;}char st[60];int tp;void PT(int x){if(x==0)putc('0');else{if(x<0){putc('-');x=-x;}while(x>0){st[++tp]=x%10+'0';x/=10;}}while(tp)putc(st[tp--]);} } using IO::getc; using IO::putc; using IO::rd; using IO::PT; int n,q; const int N=1000010; int maxa[N<<2],maxb[N<<2],tga[N<<2],tgb[N<<2]; int A[N],B[N]; void pushup(int u){maxa[u]=max(maxa[u<<1],maxa[u<<1|1]);maxb[u]=max(maxb[u<<1],maxb[u<<1|1]); } void Add(int u,int x,int y){maxa[u]+=x;maxb[u]+=y;tga[u]+=x;tgb[u]+=y; } void pushdown(int u){Add(u<<1,tga[u],tgb[u]);Add(u<<1|1,tga[u],tgb[u]);tga[u]=tgb[u]=0; } void build(int u,int l,int r){if(l==r){maxa[u]=A[l];maxb[u]=B[l];return;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u); } void update(int u,int l,int r,int L,int R,int d,bool ty){if(l==L&&r==R){if(ty) Add(u,d,0);else Add(u,0,d);return;}pushdown(u);int mid=(l+r)>>1;if(R<=mid) update(u<<1,l,mid,L,R,d,ty);else if(mid<L) update(u<<1|1,mid+1,r,L,R,d,ty);else{update(u<<1,l,mid,L,mid,d,ty);update(u<<1|1,mid+1,r,mid+1,R,d,ty);}pushup(u); } pr ans[N<<2]; void pre(int u,int l,int r,int L,int R){if(l==L&&r==R){ans[u]=pr(maxa[u],maxb[u]);return;}pushdown(u);int mid=(l+r)>>1;if(R<=mid){pre(u<<1,l,mid,L,R);ans[u]=ans[u<<1];}else if(mid<L){pre(u<<1|1,mid+1,r,L,R);ans[u]=ans[u<<1|1];}else{pre(u<<1,l,mid,L,mid);pre(u<<1|1,mid+1,r,mid+1,R);ans[u].FR=max(ans[u<<1].FR,ans[u<<1|1].FR);ans[u].SE=max(ans[u<<1].SE,ans[u<<1|1].SE);} } int solve(int u,int l,int r,int L,int R){if(l==L&&r==R){if(l==r) return min(maxa[u],maxb[u]);int mid=(l+r)>>1;pushdown(u);int s1=maxa[u<<1],s2=maxb[u<<1|1];if(s1>s2) return min(s1,max(s2,solve(u<<1,l,mid,l,mid)));else return min(s2,max(s1,solve(u<<1|1,mid+1,r,mid+1,r)));} int mid=(l+r)>>1;if(R<=mid) return solve(u<<1,l,mid,L,R);else if(mid<L) return solve(u<<1|1,mid+1,r,L,R);else{int s1=ans[u<<1].FR,s2=ans[u<<1|1].SE;if(s1>s2) return min(s1,max(s2,solve(u<<1,l,mid,L,mid)));else return min(s2,max(s1,solve(u<<1|1,mid+1,r,mid+1,R)));} } char opt[10]; int main(){rd(n);rd(q);for(int i=1;i<=n;i++) rd(A[i]);for(int i=1;i<=n;i++) rd(B[i]);build(1,1,n);int l,r,d;while(q--){char c=getc();while(c!='A'&&c!='B')c=getc();rd(l);rd(r);rd(d);if(c=='A')update(1,1,n,l,r,d,1);else update(1,1,n,l,r,d,0);rd(l);rd(r);pre(1,1,n,l,r);PT(solve(1,1,n,l,r));putc('\n');} IO::flush();return 0; }

總結(jié)

以上是生活随笔為你收集整理的[XSY4170] 妹子（线段树上二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。