线段树上二分
cpp
// 求max(a_l,..a_r)=min(b_l,....,b_r)的[l,r]数量
//mx单增，mn是单减，枚举左端点，二分第一个(mx>=mn)的位置L，第一个(mx>mn)的位置R,答案为R-L
struct Node{
int l,r,mx,mn;
};
struct SegmentTree{
vector<Node> t;
int n,MX,MN;
void init(int n){
t=vector<Node> (n<<2);
}
void pushup(int p){
t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
}
void build(int p,int l,int r,vector<int>&a,vector<int>&b){
t[p]={l,r,0,0};
if(l==r){
t[p].mx=a[l];
t[p].mn=b[l];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid,a,b);
build(p<<1|1,mid+1,r,a,b);
pushup(p);
}
int query1(int p,int l,int r){//找大于
int mid=t[p].l+t[p].r>>1;
if(l<=t[p].l&&r>=t[p].r){
int tmx=max(MX,t[p].mx);
int tmn=min(MN,t[p].mn);
if(tmx<=tmn){
MX=tmx;
MN=tmn;
return t[p].r+1;
}
if(t[p].l==t[p].r)return t[p].l;
int now=query1(p<<1,l,r);
if(now==mid+1)return query1(p<<1|1,l,r);
return now;
}
if(l<=mid&&r>mid){
int now=query1(p<<1,l,r);
if(now==mid+1)return query1(p<<1|1,l,r);
return now;
}
if(l<=mid)return query1(p<<1,l,r);
return query1(p<<1|1,l,r);
}
int query2(int p,int l,int r){//找大于等于
int mid=t[p].l+t[p].r>>1;
if(l<=t[p].l&&r>=t[p].r){
int tmx=max(MX,t[p].mx);
int tmn=min(MN,t[p].mn);
if(tmx<tmn){
MX=tmx;
MN=tmn;
return t[p].r+1;
}
if(t[p].l==t[p].r)return t[p].l;
int now=query2(p<<1,l,r);
if(now==mid+1)return query2(p<<1|1,l,r);
return now;
}
if(l<=mid&&r>mid){
int now=query2(p<<1,l,r);
if(now==mid+1)return query2(p<<1|1,l,r);
return now;
}
if(l<=mid)return query2(p<<1,l,r);
return query2(p<<1|1,l,r);
}
void clear(){
MX=-INF;
MN=INF;
}
};