这个还是看代码,比讲的清楚
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define ls (rt<<1) #define rs (rt<<1|1) using namespace std; const int maxn=5e4+5; int n,m; struct tree{ int lmx,rmx,mx,lazy,len; }t[maxn<<2]; void push_down(int rt){ if(!t[rt].lazy) return; if(t[rt].len==1){ t[rt].lazy=0; return; } if(t[rt].lazy==1){ t[ls].lmx=t[ls].rmx=t[ls].mx=t[ls].len; t[ls].lazy=1; t[rs].lmx=t[rs].rmx=t[rs].mx=t[rs].len; t[rs].lazy=1; } if(t[rt].lazy==2){ t[ls].lmx=t[ls].rmx=t[ls].mx=0; t[ls].lazy=2; t[rs].lmx=t[rs].rmx=t[rs].mx=0; t[rs].lazy=2; } t[rt].lazy=0; } void push_up(int rt){ //lmx if(t[ls].lmx==t[ls].len){ t[rt].lmx=t[ls].len+t[rs].lmx; } else if(t[ls].lmx!=t[ls].len){ t[rt].lmx=t[ls].lmx; } //rmx if(t[rs].rmx==t[rs].len){ t[rt].rmx=t[rs].len+t[ls].rmx; } else if(t[rs].rmx!=t[rs].len){ t[rt].rmx=t[rs].rmx; } //mx t[rt].mx=max(max(t[ls].mx,t[rs].mx),t[ls].rmx+t[rs].lmx); } void build(int rt,int l,int r){ t[rt].len=r-l+1; t[rt].lazy=0; t[rt].lmx=t[rt].rmx=t[rt].mx=t[rt].len; if(l==r){ return; } int mid=l+r>>1; build(ls,l,mid);build(rs,mid+1,r); } void update(int rt,int ql,int qr,int op,int l=1,int r=n){ if(ql<=l&&r<=qr){ if(op==1){//退房 t[rt].lmx=t[rt].rmx=t[rt].mx=t[rt].len; t[rt].lazy=1; } if(op==2){ t[rt].lmx=t[rt].rmx=t[rt].mx=0; t[rt].lazy=2; } return; } push_down(rt); int mid=l+r>>1; if(ql<=mid) update(ls,ql,qr,op,l,mid); if(qr>mid) update(rs,ql,qr,op,mid+1,r); push_up(rt); } int query(int rt,int x,int l=1,int r=n){ if(l==r){ return l; } push_down(rt); int mid=l+r>>1,ans=0; if(t[ls].mx>=x) ans= query(ls,x,l,mid); else if(t[ls].rmx+t[rs].lmx>=x) ans= mid-t[ls].rmx+1; else ans= query(rs,x,mid+1,r); push_up(rt); return ans; } int main(){ fastio; //freopen("lys.in","r",stdin); cin>>n>>m; build(1,1,n); for(int i=1;i<=m;i++){ int op;cin>>op; if(op==1){ int x; cin>>x; if(t[1].mx>=x) { int pos=query(1,x); cout<<pos<<endl; update(1,pos,pos+x-1,2); } else cout<<0<<endl; } else { int x,y; cin>>x>>y; update(1,x,x+y-1,1); } } }
标签:rt,int,线段,Hotel,mid,ls,ans,USACO08FEB,query From: https://www.cnblogs.com/liyishui2003/p/17263834.html