枚举最大值+ds：1887D

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

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

肯定要离线

感觉分治？

---

枚举左边区间最大值

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

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

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

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

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

---

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

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

扫描线即可

#include
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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114