锐客网

  1. 首页 > it技术 > >

线段树|[CF377D][线段树][扫描线]Developing Game

线段树扫描线

CF377D
【线段树|[CF377D][线段树][扫描线]Developing Game】把 l , r l,r l,r看成两维坐标，假设最后有解，那一定存在一个 ( L , R ) (L,R) (L,R)使得 L ≥ m a x { l [ i ] } ， L ≤ m i n { v [ i ] } L\ge max\{l[i]\}，L\le min\{v[i]\} L≥max{l[i]}，L≤min{v[i]}且 R ≥ m a x { v [ i ] } ， R ≤ m i n { r [ i ] } R\ge max\{v[i]\}，R\le min\{r[i]\} R≥max{v[i]}，R≤min{r[i]}，否则显然不满足条件
即是把 l , v , r l,v,r l,v,r看作一个横坐标 ( l , v ) (l,v) (l,v)纵坐标 ( v , r ) (v,r) (v,r)的矩形，要求尽量多的矩形使得它们的面积并不为空（可以为0，就是矩形并为一个点的情况）
那就可以线段树+扫描线了
Code：

#include #define pb push_back using namespace std; inline int read(){ int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } const int N=3e5+5; namespace segtree{ struct seg{int l,r,add,mxv,mxr; }tr[N<<2]; #define ls tr[k].l #define rs tr[k].r #define mid (ls+rs>>1) inline void pushup(int k){ if(tr[k<<1].mxv>tr[k<<1|1].mxv) tr[k].mxr=tr[k<<1].mxr; else tr[k].mxr=tr[k<<1|1].mxr; tr[k].mxv=max(tr[k<<1].mxv,tr[k<<1|1].mxv); } inline void pushadd(int k,int v){tr[k].add+=v; tr[k].mxv+=v; } inline void pushdown(int k){ if(tr[k].add){ pushadd(k<<1,tr[k].add); pushadd(k<<1|1,tr[k].add); tr[k].add=0; } } inline void build(int k,int l,int r){ ls=l,rs=r,tr[k].mxr=r,tr[k].mxv=0; if(l==r) return; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } inline void modify(int k,int ql,int qr,int v){ if(qrrs) return; if(ql<=ls && rs<=qr) return pushadd(k,v); pushdown(k); if(qr<=mid) modify(k<<1,ql,qr,v); else if(ql>mid) modify(k<<1|1,ql,qr,v); else modify(k<<1,ql,mid,v),modify(k<<1|1,mid+1,qr,v); pushup(k); } } using namespace segtree; struct sqr{ int l,r,id; sqr(){} sqr(int _l,int _r,int _id):l(_l),r(_r),id(_id){} }; vector>add[N],del[N]; int x[N],y[N],v[N]; int mx=0,ansl,ansr; int ans[N],cnt=0; int main(){ build(1,1,300000); int n=read(); for(int i=1; i<=n; i++){ x[i]=read(); v[i]=read(); y[i]=read(); int l=x[i],r=y[i]; add[l].pb(sqr(v[i],r,i)); del[v[i]].pb(sqr(v[i],r,i)); } for(int i=1; i<=300000; i++){ for(int j=0; jmx){mx=nmx,ansl=i; ansr=tr[1].mxr; } for(int j=0; j=ansr && v[i]>=ansl && v[i]<=ansr) ans[++cnt]=i; for(int i=1; i<=cnt; i++) cout<

    推荐阅读


    上一篇：倍增|191026考试题解

    下一篇：线段树|191024省选测试题解