【LOJ #2346】「JOI 2016 Final」断层（线段树）

传送门

把坐标$(x,y)\to (x-y,x+y)$ 后发现就是往下和右移$2l$长度

对于$x,y$分别维护一颗线段树 线段树上二分开始移的位置区间加即可

#include<bits/stdc++.h> using namespace std; #define re register #define cs const #define pb push_back #define ll long long #define pii pair<int,int> #define fi first #define se second #define bg begin #define poly vector<int> cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return ib==ob?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;} template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;} cs int N=200005; ll ansx[N],ansy[N]; namespace tx{ #define lc (u<<1) #define rc ((u<<1)|1) #define mid ((l+r)>>1) ll mx[N<<2],tag[N<<2]; inline void pushup(int u){ mx[u]=min(mx[lc],mx[rc]); } inline void pushnow(int u,ll k){ mx[u]+=k,tag[u]+=k; } inline void pushdown(int u){ if(!tag[u])return; pushnow(lc,tag[u]),pushnow(rc,tag[u]); tag[u]=0; } void build(int u,int l,int r){ if(l==r){mx[u]=l;return;} build(lc,l,mid),build(rc,mid+1,r); pushup(u); } void get(int u,int l,int r){ if(l==r){ansx[l]=mx[u];return;} pushdown(u),get(lc,l,mid),get(rc,mid+1,r); } void update(int u,int l,int r,int st,int des,ll k){ if(st<=l&&r<=des)return pushnow(u,k); pushdown(u); if(st<=mid)update(lc,l,mid,st,des,k); if(mid<des)update(rc,mid+1,r,st,des,k); pushup(u); } int find(int u,int l,int r,int x){ if(l==r)return l; pushdown(u); if(mx[u]>x)return 0; if(mx[rc]<=x)return find(rc,mid+1,r,x); return find(lc,l,mid,x); } } namespace ty{ ll mx[N<<2],tag[N<<2]; inline void pushup(int u){ mx[u]=min(mx[lc],mx[rc]); } inline void pushnow(int u,ll k){ mx[u]+=k,tag[u]+=k; } inline void pushdown(int u){ if(!tag[u])return; pushnow(lc,tag[u]),pushnow(rc,tag[u]); tag[u]=0; } void build(int u,int l,int r){ if(l==r){mx[u]=l;return;} build(lc,l,mid),build(rc,mid+1,r); pushup(u); } void get(int u,int l,int r){ if(l==r){ansy[l]=mx[u];return;} pushdown(u),get(lc,l,mid),get(rc,mid+1,r); } void update(int u,int l,int r,int st,int des,ll k){ if(st<=l&&r<=des)return pushnow(u,k); pushdown(u); if(st<=mid)update(lc,l,mid,st,des,k); if(mid<des)update(rc,mid+1,r,st,des,k); pushup(u); } int find(int u,int l,int r,int x){ if(l==r)return l; pushdown(u); if(mx[u]>x)return 0; if(mx[rc]>x)return find(lc,l,mid,x); return find(rc,mid+1,r,x); } #undef lc #undef rc #undef mid } int n,q; int X[N],D[N],L[N]; int main(){ #ifdef Stargazer freopen("lx.cpp","r",stdin); #endif n=read(),q=read(); for(int i=1;i<=q;i++)X[i]=read(),D[i]=read(),L[i]=read(); tx::build(1,1,n),ty::build(1,1,n); for(int i=q;i;i--){ int x=X[i],d=D[i],l=L[i]; if(d==1){ int pos=tx::find(1,1,n,x); if(pos)ty::update(1,1,n,1,pos,-2*l); } else{ int pos=ty::find(1,1,n,x)+1; if(pos<=n)tx::update(1,1,n,pos,n,2*l); } } tx::get(1,1,n),ty::get(1,1,n); for(int i=1;i<=n;i++)cout<<(ansx[i]-ansy[i])/2<<'\n'; }