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< 推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客 C. 子段乘积（线段树）
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间