「JOISC 2020 Day1」扫除（分治）（线段树）（平衡树）

本文主要是介绍「JOISC 2020 Day1」扫除（分治）（线段树）（平衡树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

首先考虑 $Subtask\ 3$ ，这些点是单调的，所以用线段树维护区间赋值
$Subtask\ 4$ ，没有插入，考虑如果一个点被推到一个地方，那么它与其它的相对顺序就不会变，所以我们用动态开点线段树来找点，用一个平衡树来维护被推的点，平衡树支持插入，区间赋值
对于有插入的情况，即对于 $k$ 号询问，需要把 $l_k,r_k]$ 的修改对 $k$ 做一遍，那么我们线段树分治，每次处理 $[l, r]$ 的时候把 $[l, r]$ 的修改做一遍统计对这些询问的影响
复杂度 $O((M+Q)\log N\log Q)$ ， $C o d e$ ，太慢了没卡过！
其实还有一种方法，就是考虑如果只有从左向右推的话，最后 $x$ 的坐标是个关于 $y$ 的分段函数，我们按 $y$ 和修改的高度从大到小排序，每一个修改可以表示为将 $\le x$ 的一段区间推到 $x$ ，可以用线段树维护，考虑有上下推的时候对一个左右推的干扰，上下推可以把一些点扫走，于是左右推的实质是将 $[l, r]$ 的点推到 $r$ ，预处理出这个 $l$ 就可以了，这个 $l$ 是之前出现的上下推的宽度的最大值，同样用线段树维护，具体可以看代码

#include<bits/stdc++.h>
#define cs const
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pi;
cs int N = 2e6 + 50;
namespace IO{inline char gc(){static cs int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2;return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}template<typename T>T Read(){char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x;}inline int read(){return Read<int>();}
} using namespace IO;
int n, m, Q;
int x[N], y[N], opt[N], vl[N];
pi as[N];
cs int M = N * 30;
cs int INF = 1e9 + 7;
struct SegmenTree{#define mid ((l+r)>>1)int ls[M], rs[M], mx[M], rt, nd;vector<pi> S;void clr(){ rt=nd=0; }int newnode(){ int x=++nd; ls[x]=rs[x]=mx[x]=0; return x; }void modify(int &x, int l, int r, int L, int R, int v){if(L>R) return;if(!x) x=newnode(); if(mx[x]>=v) return;if(L<=l&&r<=R){ mx[x]=v; return; } if(L<=mid) modify(ls[x],l,mid,L,R,v);if(R>mid) modify(rs[x],mid+1,r,L,R,v);}int query(int x, int l, int r, int p){if(!x) return 0; if(l==r) return mx[x];if(p<=mid) return max(mx[x],query(ls[x],l,mid,p));else return max(mx[x],query(rs[x],mid+1,r,p));}#undef mid
}X, Y;
void upt(int op, int vl){int t = op ? X.query(X.rt,0,n,vl) : Y.query(Y.rt,0,n,vl);op ? Y.S.pb(pi(vl,t)) : X.S.pb(pi(vl,t)); op ? Y.modify(Y.rt,0,n,t,n-vl-1,vl+1) : X.modify(X.rt,0,n,t,n-vl-1,vl+1);
}
namespace SGT{bool vis[N];vector<pi> S[N<<2];#define mid ((l+r)>>1)void ins(int x, int l, int r, int L, int R, pi v){if(L<=l&&r<=R){ S[x].pb(v); return; }if(L<=mid) ins(x<<1,l,mid,L,R,v); if(R>mid) ins(x<<1|1,mid+1,r,L,R,v);}void subwork(int x, int l, int r){if(!S[x].size()) return;X.clr(), Y.clr(); X.S.clear(), Y.S.clear();for(int i=l; i<=r; i++) if(opt[i]==2||opt[i]==3) upt(opt[i]==2,vl[i]);X.clr(), Y.clr();sort(S[x].begin(),S[x].end(),[](cs pi &a, cs pi &b){ return ::y[a.fi] > ::y[b.fi]; });sort(Y.S.begin(), Y.S.end(), [](cs pi &a, cs pi &b){ return a.fi > b.fi; }); int j=0; for(auto c : S[x]){int u = c.fi;for(;j<(int)Y.S.size()&&Y.S[j].fi>=::y[u];j++){Y.modify(Y.rt,0,n,Y.S[j].se,n-Y.S[j].fi,n-Y.S[j].fi);} ::x[u]=max(::x[u],Y.query(Y.rt,0,n,::x[u]));}sort(S[x].begin(),S[x].end(),[](cs pi &a, cs pi &b){ return ::x[a.fi] > ::x[b.fi]; });sort(X.S.begin(), X.S.end(), [](cs pi &a, cs pi &b){ return a.fi > b.fi; }); j=0; for(auto c : S[x]){int u = c.fi;for(;j<(int)X.S.size()&&X.S[j].fi>=::x[u];j++){X.modify(X.rt,0,n,X.S[j].se,n-X.S[j].fi,n-X.S[j].fi);} ::y[u]=max(::y[u],X.query(X.rt,0,n,::y[u]));}for(auto c : S[x]) as[c.se]=pi(::x[c.fi],::y[c.fi]);}void work(int x, int l, int r){subwork(x,l,r); if(l^r) work(x<<1,l,mid), work(x<<1|1,mid+1,r);} #undef mid
}
int main(){n=read(), m=read(), Q=read();for(int i=1; i<=m; i++) x[i]=read(), y[i]=read();static int las[N]; int q=0;for(int i=1; i<=Q; i++){opt[i]=read();if(opt[i]==1){ int x=read(); SGT::ins(1,1,Q,las[x]+1,i,pi(x,++q)); las[x]=i; }if(opt[i]==2||opt[i]==3) vl[i]=read();if(opt[i]==4) x[++m]=read(), y[m]=read(), las[m]=i;}SGT::work(1,1,Q); for(int i=1; i<=q; i++) cout<<as[i].fi<<" "<<as[i].se<<'\n';return 0;
}