Luogu P3028 [USACO10OCT]汽水机Soda Machine

题目链接：传送门

离散化一下维护一个最值
啊学数据结构学傻了

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<complex>#include<algorithm>#include<climits>#include<queue>#include<map>#include<set>#include<vector>#include<iomanip>#defineA 1000010#defineB 2010usingnamespacestd;typedeflonglongll;structnode{intx,y;}e[A];intn,t[A],cnt,mx;structT{intl,r,w,f;}tree[A];voidbuild(intk,intl,intr){tree[k].l=l;tree[k].r=r;if(l==r)return;intm=(l+r)>>1;build(k<<1,l,m);build(k<<1|1,m+1,r);}voiddown(intk){tree[k<<1].f+=tree[k].f;tree[k<<1|1].f+=tree[k].f;tree[k<<1].w+=tree[k].f;tree[k<<1|1].w+=tree[k].f;tree[k].f=0;}voidadd(intk,intl,intr){if(tree[k].l>=landtree[k].r<=r){tree[k].w++;tree[k].f++;return;}if(tree[k].f)down(k);intm=(tree[k].l+tree[k].r)>>1;if(l<=m)add(k<<1,l,r);if(r>m)add(k<<1|1,l,r);tree[k].w=max(tree[k<<1].w,tree[k<<1|1].w);}intmain(intargc,charconst*argv[]){cin>>n;for(inti=1;i<=n;i++)cin>>e[i].x>>e[i].y,t[++cnt]=e[i].x,t[++cnt]=e[i].y;sort(t+1,t+cnt+1);intm=unique(t+1,t+cnt+1)-t-1;for(inti=1;i<=n;i++)e[i].x=lower_bound(t+1,t+m+1,e[i].x)-t,e[i].y=lower_bound(t+1,t+m+1,e[i].y)-t,mx=max(mx,max(e[i].x,e[i].y));build(1,1,mx);for(inti=1;i<=n;i++)add(1,e[i].x,e[i].y);cout<<tree[1].w<<endl;}