我们发现
也就是说,在某个位置执行 等价于把其后的所有 min 和 max 操作的权值减去 ,所有 min 和 max 执行完后再加上 。因此 是分段函数且分成三段。
于是我们用树状数组维护的是所有加法操作权值的前缀和,用线段树维护 min 和 max 操作(区间加法全局求 min/max)。验题人则直接把三个操作写在了一棵线段树里面,不需要繁琐的区间加。
合并信息时,注意信息合并的本质是两个分段函数的复合,而不是简单的区间交(我按照区间交写挂了好久才想到是 pushup 的锅)
Rg un(const Rg& a,const Rg& b){ return Rg(max(min(a.l,b.r),b.l),max(min(a.r,b.r),b.l)); }
完整代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; typedef long long ll; const ll inf=1145****19810000; #define il inline #define SET #define TO = const int N=100005; int n; struct Rg{ ll l,r;bool ls; // 0->min 1->max Rg(ll l=-inf,ll r=inf,bool ls=0):l(l),r(r){} ll operator()(ll a){if(ls==0) return min(max(a,l),r); else return max(min(a,r),l); } Rg operator+(const ll& o){ return Rg(l+o,r+o); } }; Rg un(const Rg& a,const Rg& b){ return Rg(max(min(a.l,b.r),b.l),max(min(a.r,b.r),b.l),b.ls); } const Rg I(-inf,inf); Rg v[N<<1];ll tg[N<<1];int ch[N<<1][2];int tp=0; #define ls ch[u][0] #define rs ch[u][1] void pushup(int u){ v[u]=un(v[ls],v[rs]); } void apply(int u,ll t){ v[u].l+=t;v[u].r+=t;tg[u]+=t; } void pushdown(int u){ if(tg[u]){ if(ls) apply(ls,tg[u]); if(rs) apply(rs,tg[u]); tg[u]=0; } } int build(Rg a[],int l,int r){ if(l==r){ v[++tp]=a[l];return tp; } else{ int mid=(l+r)/2,u=++tp; ls=build(a,l,mid); rs=build(a,mid+1,r); pushup(u); return u; } } void add(int L,int R,ll t,int u,int l,int r){ pushdown(u); if(L<=l && r<=R){ apply(u,t); } else{ int mid=(l+r)/2; if(L<=mid){ add(L,R,t,ls,l,mid); } if(R>mid){ add(L,R,t,rs,mid+1,r); } pushup(u); } } void upd(int P,Rg t,int u,int l,int r){ pushdown(u); if(l==r) v[u]=t; else{ int mid=(l+r)/2; if(P<=mid) upd(P,t,ls,l,mid); else upd(P,t,rs,mid+1,r); pushup(u); } } Rg a[N];ll ad[N]; ll sb[N]; void adds(int u,ll t){ while(u<=n){ sb[u]+=t;u+=(u&(-u)); } } ll querys(int u){ ll t=0;while(u){ t+=sb[u];u-=(u&(-u)); }return t; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ int op;ll v;cin>>op>>v; if(op==1){ a[i]=I;ad[i]=v; } if(op==2){ a[i]=Rg(-inf,v);ad[i]=0; } if(op==3){ a[i]=Rg(v,inf,1);ad[i]=0; } adds(i,ad[i]); } int Rt=build(a,1,n); for(int i=1;i<=n;i++){ add(i,n,-ad[i],Rt,1,n); } int q; cin>>q; // Seg[i] -> a[i] - Sum[i] for(int _=1;_<=q;_++){ int op;cin>>op; if(op==1){ int p;ll v;cin>>p>>v; // ad[p] -> v; add(p,n,-v+ad[p],Rt,1,n); adds(p,v-ad[p]); SET ad[p] TO v; // a[p] -> I; SET a[p] TO I; upd(p,I,Rt,1,n); }else if(op==2){ int p;ll v;cin>>p>>v; // ad[p] -> 0 add(p,n,ad[p],Rt,1,n); adds(p,-ad[p]); SET ad[p] TO 0; // a[p] -> Rg(-inf,v) SET a[p] TO Rg(-inf,v); upd(p,a[p]+(-querys(p)),Rt,1,n); }else if(op==3){ int p;ll v;cin>>p>>v; // ad[p] -> 0 add(p,n,ad[p],Rt,1,n); adds(p,-ad[p]); SET ad[p] TO 0; // a[p] -> Rg(v,inf) SET a[p] TO Rg(v,inf,1); upd(p,a[p]+(-querys(p)),Rt,1,n); }else{ ll x;cin>>x; Rg res=v[Rt]; cout<<res(x)+querys(n)<<"\n"; } } return 0; }
全部评论
(0) 回帖