电子商务网站建设功能建网站视频

https://codeforces.com/problemset/problem/1887/D

左边区间最大值小于右边区间最小值

肯定要离线

感觉分治？

枚举左边区间最大值

求出其影响范围，推出左端点可取范围

然后可取右端点就是一段连续大于此值得区间

也就是左端点在一段区间时右端点可以在另一端区间取

差分一下，拿个数据结构维护即可

发现枚举最大值过程从大往小枚举最优。求范围set即可

后面官方题解有另一种理解

映射到坐标系上，相当于一堆矩形，询问点是否在矩形内

扫描线即可

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 300010
//#define M
//#define mo
struct node {int x, id; 
}b[N];
struct Node {int x, l, r, op; 
}a[N<<2];
int n, m, i, j, k, T;
int ans[N], l, r, q; 
set<int>s, Nots; 
set<int>::iterator it1, it2, it3; bool cmp(Node x, Node y) {if(x.x == y.x) return x.op < y.op; return x.x < y.x; 
}struct Sline {int i, k, rt; struct Segment_tree {int tot, ls[N<<2], rs[N<<2]; int s[N<<2]; void build(int &k, int l, int r) {if(!k) k=++tot; if(l==r) return ; int mid=(l+r)>>1; build(ls[k], l, mid); build(rs[k], mid+1, r); }void push_down(int k) {s[ls[k]]+=s[k]; s[rs[k]]+=s[k]; s[k]=0; }void add(int k, int l, int r, int x, int y, int z) {if(l>=x && r<=y) return s[k]+=z, void(); int mid=(l+r)>>1; push_down(k); if(x<=mid) add(ls[k], l, mid, x, y, z); if(y>=mid+1) add(rs[k], mid+1, r, x, y, z); }int que(int k, int l, int r, int x) {if(l==r) return s[k]; int mid=(l+r)>>1; push_down(k); if(x<=mid) return que(ls[k], l, mid, x); else return que(rs[k], mid+1, r, x); }}Seg;void add_op(int lx, int rx, int ly, int ry) {
//		printf("[%d %d] [%d %d]\n", lx, rx, ly, ry); a[++k].x=ly; a[k].l=lx; a[k].r=rx; a[k].op=1; a[++k].x=ry+1; a[k].l=lx; a[k].r=rx; a[k].op=-1; }void add_que(int l, int r, int i) {a[++k].x=r; a[k].l=l; a[k].r=i; a[k].op=2; }void calc() {sort(a+1, a+k+1, cmp); Seg.build(rt, 1, n); for(i=1; i<=k; ++i) {if(a[i].op < 2) {
//				printf("Add %d [%d %d] %d\n", a[i].x, a[i].l, a[i].r, a[i].op); Seg.add(1, 1, n, a[i].l, a[i].r, a[i].op); }else {ans[a[i].r]=Seg.que(1, 1, n, a[i].l); 
//				printf("Que : %d | %d(%d)\n", a[i].l, ans[a[i].r], a[i].r); }}}
}San;signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1; i<=n; ++i) b[i].x=read(), b[i].id=i; sort(b+1, b+n+1, [] (node x, node y) { return x.x>y.x; }); for(i=1; i<=n+1; ++i) Nots.insert(i); s.insert(0); s.insert(n+1); for(j=1; j<=n; ++j) {i = b[j].id; it1 = it2 = s.lower_bound(i); --it1; it3 = Nots.lower_bound(*it2); s.insert(i); Nots.erase(i); San.add_op((*it1)+1, i, (*it2), (*it3)-1); }q=read(); for(i=1; i<=q; ++i) {l = read(); r = read(); San.add_que(l, r, i); }San.calc(); for(i=1; i<=q; ++i) printf(ans[i] ? "Yes\n" : "No\n"); return 0;
}