CF2111 总结

First Post:

Last Update:

Word Count:
4.9k

Read Time:
25 min

Page View: loading...

CF2111 总结

A

翻译

有三个能量水晶，标号为 ，每个能量水晶有一个充能值 。一次操作可以让任意水晶的充能值上升任意正整数，但必须满足 。现要让每一个水晶的充能值均变为恰好给定正整数 ，问最少需要的操作次数。 组数据。

题解

观察到限制等价于 。容易发现 具有对称性，不妨设 ，容易发现通过三次操作可以让这三个充能值都变为 。（先让 变为 ，再对 重复）因此，若要让每个水晶的充能值都变为 ，最少需要的操作次数 。因此直接贪心模拟每次操作即可。

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
void solve(int x) {
	int a[3] = {0, 0, 0}, opt = 0 ;
	while(!((a[0] == x) && (a[1] == x) && (a[2] == x))) {
		int mnp=0; f(i,1,2) if(a[i] < a[mnp]) mnp = i;
		int secmx=0x3f3f3f3f; f(i,0,2) if((i != mnp) && (a[i] < secmx)) secmx = a[i];
		a[mnp] = min(x, secmx * 2 + 1); ++opt;
	}
	cout << opt << '\n';
}
int main() {
	int t=rd(); while(t--) {
		solve(rd());
	}
	return 0;
}

// 0 0 0
// 1 0 0
// max ai / 2 <= min ai

B

翻译

给定 个 的长方体，判断是否能将以前 个 数作为棱长的正方体箱子放入该长方体内，正方体的每条棱都与一条长方体的棱平行，且正方体不能悬空。 组数据。。其中 数满足 。

题解

容易发现若能将最大的两个箱子放入，不妨假设第一个箱子紧贴长方体下底面右后角放置，第二个箱子紧贴长方体右后角且放置在第一个箱子上，则第三个箱子必能放入第二个箱子左边，第一个箱子上面的位置（这是由于 ），以此类推，若能将最大的两个箱子放入，则必能将全部箱子放入。旋转 分别判断即可。

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
int f[11];
bool fit(int x, int y, int z, int t) {
	return (x >= f[t]) && (y >= f[t]) && (z >= f[t] + f[t-1]) ;
}
bool test(int x, int y, int z, int t) {
	return fit(x, y, z, t) | fit(x, z, y, t) | fit(y, x, z, t) | fit(y, z, x, t) | fit(z, x, y, t) | fit(z, y, x, t);
}
int main() {
	f[1] = 1; f[2] = 2; f(i,3,10) f[i] = f[i-1] + f[i-2];
	int t = rd(); while(t--) {
		int n = rd(), m = rd();
		f(i,1,m) {
			int w = rd(), l = rd(), h = rd();
			cout << test(w, l, h, n);
		}
		cout << '\n';
	}
	return 0;
}

C

翻译

给定 与数组 。一次操作可以选择任一位置 ，选择一项：

  • 对于所有 ，令 ，代价为 。

  • 对于所有 ，令 ，代价为 。

要让 的值变为全部相同，求最小的代价。 组数据。。

题解

考察最后 ，容易发现最后的代价最小值为 操作涉及的数的数量的总和的最小值（下简称总次数）。考察 在原数列中的所有出现。容易发现对于一个全为 的连续段，我们可以在首尾分别操作，节省出等同于连续段长的总次数。容易发现这就是最小代价（注意到最优解中一个数一定不会被操作复数次，因此节省的操作一定是原本是 的数贡献的，而若一个 未被操作，意味着其前面的 没有执行向后的操作，其后面的 没有执行向前的操作，若两个贡献节省的操作的 中间有非 的数，则这个数一定不会被操作，矛盾）。直接验证即可。

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
int a[500005]; vector<int> pos[500005];
int main() {
	int t = rd(); while(t--) {
		int n = rd(); f(i,1,n) rd(a[i]), pos[a[i]].pb(i);
		ll mc = (1LL<<60LL);
		f(i,1,n) {
			ll mnc = (1LL<<60LL), len = pos[i].size();
			if(pos[i].size()) {
				if(pos[i].size() == 1) mnc = 1LL * (n-1) * i;
				else {
					for(int x = 0, y; x < len; x = y + 1) {
						y = x; while((y+1 < len) && (pos[i][y+1] == pos[i][y] + 1)) ++y;
						mnc = min(mnc, 1LL * (n - (y-x+1)) * i) ;
					}
				}
			}
			mc = min(mc, mnc);
			pos[i].clear();
		}
		cout << mc << '\n';
	}
	return 0;
}

D

翻译

有 个小组要上 节课，，每个小组的第 节课都不能占据相同的教室。有 个教室，每个教室由楼层和门牌号组成，具体来说，第 个门牌号是一个数 ，而其所在的楼层 满足 ，一个教室的索引值 ，保证每个教室的 不同，且 。若某小组相邻的两节课所在的教室楼层不同，则会付出等同于这两个楼层差的绝对值的代价。请你为这 个小组规划教室，最大化代价。 组数据。。

题解

容易发现对于任意一个小组，其上课的楼层按顺序一定是 ，因此问题被我们简化为了只有两节课的情况。

将楼层排序，不妨设 ，设第 个小组第一节课在 教室，第二节课在 教室。总代价即为 。

容易发现，如果某个 ，则我们一定尽量将其往前。反之则将其往后。对于 也同理。因此， 与 均为靠头尾的两段连续段且长度有关联。不妨 的头部长度为 ，尾部长度为 ，易知 的头部长度为 ，尾部长度为 。则代价即为 ，易知 时代价取最大值。

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
int n, m, a[100005];
int main() {
	int t = rd(); while(t--) {
		n = rd(); m = rd(); f(i,1,m) a[i] = rd() ;
		sort(a+1, a+m+1) ;
		int ans = 0; int o = (n&1), tn = n - o;
		f(i,1,(tn>>1)) {
			f(t,0,5) cout << ( (t&1) ? (a[m-i+1]) : (a[i]) ) << ' ';
			ans += 5 * ((a[m-i+1] / 100) - (a[i] / 100)) ;
			cout << '\n' ;
			f(t,0,5) cout << ( (t&1) ? (a[i]) : (a[m-i+1]) ) << ' ';
			ans += 5 * ((a[m-i+1] / 100) - (a[i] / 100)) ;
			cout << '\n' ;
		}
		if(o) {
			int i = (tn>>1) + 1;
			f(t,0,5) cout << ( (t&1) ? (a[m-i+1]) : (a[i]) ) << ' ';
			ans += 5 * ((a[m-i+1] / 100) - (a[i] / 100)) ;
			cout << '\n' ;
		}
		cerr << ans << '\n';
	}
	return 0;
}

// n group
// m classroom

// 1 group ~ 6 class

E

翻译

给定一个长度为 ，由 组成的字符串，有 次操作，每次操作给定两个字符 ，代表可以将字符串中的一个字符 改为 。现在按顺序依次执行这 次操作（每次操作也可以选择不执行），最小化操作完成后字符串的字段序。 组数据。。

题解

考虑对于每个位置上的字符的操作，仅有可能为以下几种：

  • P:
  • Q:
  • R:
  • S:
  • T:

容易发现我们只需要贪心的，从前往后对于每个位置尽可能最小化该位置的最终字符，即可得到最小字典序。问题出在 P, T 操作之间对于 操作的争抢。我们可能会考虑到，如果对于某个位置 A 实施了 T 操作，会不会导致 减少（而如果换成 S 操作则不会减少），从而使得后面的位置 B 无法利用 P 操作了呢？事实上这是无需担忧的，我们不妨考虑这种矛盾出现的情况，用 S 操作替换 T 操作的前提是我们可以先在 A 位置实施 S 操作，再在 B 位置实施 P 操作，这就意味着我们有 , , , 操作各一个，我们完全可以在 A 位置实施 T 操作而在 B 位置实施 Q 操作，一定不劣。

因此，对于每个位置，我们贪心的优先按照 Q > P, T > S > R 的顺序尽可能执行操作即可。

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
string str; int n, q;
set<int> B, D; vector<int> A, C; int posA, posC, bdC, bdA;
void _try(int pos) {
	if(str[pos] == 'a') return ;
	if(str[pos] == 'b') {
		if(B.size()) B.erase(B.begin()), str[pos] = 'a';
		else if(posA < bdA) {
			auto it = D.lower_bound(A[posA]);
			if(it != D.end()) ++posA, D.erase(it), str[pos] = 'a';
		}
	}
	if(str[pos] == 'c') {
		if(D.size()) D.erase(D.begin()), str[pos] = 'a';
		else if(posC < bdC){
			auto it = B.lower_bound(C[posC]);
			if(it != B.end()) ++posC, B.erase(it), str[pos] = 'a';
		}
		if(str[pos] == 'c' && posC < bdC) --bdC, str[pos] = 'b';
	}
}
void solve() {
	cin >> n >> q >> str;
	f(i,1,q) {
		char x, y; cin >> x >> y;
		if(x == 'b' && y == 'c') A.pb(i), ++bdA;
		if(x == 'b' && y == 'a') B.insert(i);
		if(x == 'c' && y == 'b') C.pb(i), ++bdC;
		if(x == 'c' && y == 'a') D.insert(i);
	}
	f(i,0,n-1) _try(i);
	cout << str << '\n' ;
	posA = posC = bdC = bdA = 0; A.clear(); C.clear(); B.clear(); D.clear();
}
int main() {
	ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) solve();
	return 0;
}

/*
operation
A:(b, c) B(b, a) C(c, b) D(c, a)

b->a: B, AD
c->b: C
c->a: D, CB
*/

F

翻译

给定一张网格纸，构造一个四连通块，使得其周长与面积的比值等于 ，无解输出 。 组数据。任一构造使用的连通块面积不得超过 。

题解

不妨设现有一个连通块面积为 ，周长为 。若新增一个方格，则 增加 ，而 增加 或 。初始状态下，。

设 增加 的次数为 , 增加 的次数为 ，则所有可能的 均应能写成 的形式。不难发现，若 ，则必有 ，若 ，则必有 。对应的构造是容易的。至此， 的问题已经处理完成。

接下来考虑 的情况。容易发现我们只需要解如下不定方程组：

容易发现该方程组一定有满足题目要求的解。简单枚举 即可。

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
void solve() {
	int p = rd(), s = rd();
	if(p >= 2 * s) {
		int res = p - 2*s;
		if(res == 0) { cout << "4\n0 0\n0 1\n1 0\n1 1\n" ; return ; }
		if((2*s) % res != 0) { cout << "-1" << '\n'; return ; }
		int x = (2*s) / res;
		cout << x << '\n' ;
		f(i,1,x) cout << 0 << ' ' << i << '\n' ;
	} else {
		if(p%2) p*=2, s*=2 ;
		for(int k = 1; ; ++k) {
			int Rp = p * k, Rs = s * k, v = (Rp - 4) / 2, a = v/2, b = v-(v/2);
			if((Rs <= (a+1) * (b+1)) && (Rs >= a + b + 1)) {
				cout << Rs << '\n' ;
				int x = Rs - (a + b + 1) ;
				f(i,1,a+1) f(j,1,b+1) {
					if((i == 1) || (j == 1)) cout << i << ' ' << j << '\n' ;
					else if(x) { --x; cout << i << ' ' << j << '\n'; }
				}
				return ;
			}
		}
	}
}
int main() {
	int t=rd(); while(t--) solve();
	return 0;
}

G

翻译

对于一个长度为 的序列，定义它是好的当且仅当它能被划分为前后两段，且前段中的所有数均大于后段中的所有数，或者后段中的所有数均大于前段中的所有数。

给定一个长度为 的排列 ， 次询问该排列中 之间的子段是否是好的。强制在线。（采用交互实现，具体参照原题）

题解

考虑若一个子段 是好的，必然存在一个 ，使得可以将这一子段划分为前后两段，且满足以下两个条件之一：

  • 前段的所有数均不大于 ，后段的所有数均大于 。

  • 前段的所有数均不小于 ，后段的所有数均小于 。

考虑逐渐令 增大来回答每个询问。记 。维护 的所有连续 01 段。容易发现这些 01 段只会发生 次变化，易于使用 std::set< tuple<int, int, int> > 维护。考虑相邻的两个连续 01 段，假设第一个连续段覆盖 ，第二个连续段覆盖 ，则对于所有 的 ，这些字段都是好的。

预处理出所有这样的三元组 ，易知这些三元组的数量是 的。对于每个三元组按照 使用主席树维护即可。具体来说，每个 在 处令 增加 1，在 处撤销这一修改。使用差分优化即可避免区间修改。

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
	int f=1, x=0; ch=getchar();
	while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
const int _ = 32e5 + 5, __ = 32e5 + 5;
int n, p[_], pos[_], q, x[_];
set< tuple<int, int, int> > blocks ;
// x[i] = (p[i] <= t) ? 1 : 0;
// (r, l, v) i in [l, r], x[i] = v
set< tuple<int, int, int> > tmp_ok;
tuple<int, int, int> ok[__]; int tot;
void updL(set< tuple<int, int, int> > :: iterator it) {
	auto itL = it; --itL;
	int l, l2, r, r2, v, v2; tie(r, l, v) = (*itL); tie(r2, l2, v2) = (*it);
	assert(l2 == r + 1);
	tmp_ok.insert(make_tuple(l, r, r2)) ;
	// (l, m, r)
	// [L, R] is ok when l <= L <= m < r <= r2
}
void updR(set< tuple<int, int, int> > :: iterator it) {
	auto itR = it; ++itR;
	int l, l2, r, r2, v, v2; tie(r, l, v) = (*it); tie(r2, l2, v2) = (*itR);
	assert(l2 == r + 1);
	tmp_ok.insert(make_tuple(l, r, r2)) ;
	// (l, m, r)
	// [L, R] is ok when l <= L <= m < r <= r2
}
void upd(int r) {
	auto it = blocks.lower_bound(make_tuple(r, 0, 0)) ;
	if(it != blocks.begin()) updL(it);
	if(it != --blocks.end()) updR(it);
}
void alter(int p) {
	x[p] = 1; // cerr << "Handle : " << p << endl;
	if(p==1) {
		if(x[p+1] == 1) {
			blocks.erase(blocks.begin()) ;
			auto it = blocks.begin(); int l, r, v; tie(r, l, v) = (*it); assert(v == 1);
			blocks.erase(it); blocks.insert(make_tuple(r, l-1, v)) ; upd(r);
		} else {
			auto it = blocks.begin(); int l, r, v; tie(r, l, v) = (*it); assert(v == 0);
			blocks.erase(blocks.begin()) ;
			blocks.insert(make_tuple(1, 1, 1)) ; blocks.insert(make_tuple(r, l+1, v)) ;
			upd(1); upd(r);
		}
		return ;
	}
	if(p==n) {
		if(x[p-1] == 1) {
			blocks.erase(--blocks.end()) ;
			auto it = --blocks.end(); int l, r, v; tie(r, l, v) = (*it); assert(v == 1);
			blocks.erase(it); blocks.insert(make_tuple(r+1, l, v)) ; upd(r+1);
		} else {
			auto it = --blocks.end(); int l, r, v; tie(r, l, v) = (*it); assert(v == 0);
			blocks.erase(it); blocks.insert(make_tuple(n, n, 1)); blocks.insert(make_tuple(r-1, l, v)) ;
			upd(n); upd(r-1);
		}
		return ;
	}
	int Lv = x[p-1], Rv = x[p+1], t = (Lv<<1) + Rv;
	if(t==0) {
		auto it = blocks.lower_bound(make_tuple(p, 0, 0)); assert(it != blocks.end()); int l, r, v; tie(r, l, v) = (*it); /*cerr << "[" << l << ", " << r << ", " << v << "]" << endl;*/ assert(v == 0);
		blocks.erase(it); blocks.insert(make_tuple(p-1, l, 0)); blocks.insert(make_tuple(r, p+1, 0)); blocks.insert(make_tuple(p, p, 1));
		upd(p-1); upd(p); upd(r);
	}
	if(t==1) {
		auto it = blocks.lower_bound(make_tuple(p, 0, 0)); int l, r, v; tie(r, l, v) = (*it); assert(v == 0); assert(r == p);
		auto it2 = it; ++it2; int l2, r2, v2; tie(r2, l2, v2) = (*it2); assert(v2 == 1);
		blocks.erase(it); blocks.erase(it2); blocks.insert(make_tuple(r-1, l, 0)); blocks.insert(make_tuple(r2, l2-1, 1));
		upd(r-1); upd(r2);
	}
	if(t==2) {
		auto it = blocks.lower_bound(make_tuple(p, 0, 0)); int l, r, v; tie(r, l, v) = (*it); assert(v == 0); assert(l == p);
		auto it2 = it; --it2; int l2, r2, v2; tie(r2, l2, v2) = (*it2); assert(v2 == 1);
		blocks.erase(it); blocks.erase(it2); blocks.insert(make_tuple(r2+1, l2, 1)); blocks.insert(make_tuple(r, l+1, 0));
		upd(r2+1); upd(r);
	}
	if(t==3) {
		auto it = blocks.lower_bound(make_tuple(p, 0, 0)), itL = it, itR = it; --itL; ++itR;
		int l, l2, r, r2, v, v2; tie(r, l, v) = (*itL); tie(r2, l2, v2) = (*itR); assert(v2 == 1); assert(v2 == 1); assert(r == p-1); assert(l2 = p+1);
		blocks.erase(it); blocks.erase(itL); blocks.erase(itR); blocks.insert(make_tuple(r2, l, 1));
		upd(r2);
	}
}

int sum[__ * 20], rt[__ << 1], ls[__ * 20], rs[__ * 20], tott;
void pushup(int p) {
	sum[p] = sum[ls[p]] + sum[rs[p]] ;
}
void modify(int o, int& p, int l, int r, int q, int x) {
	if(q>r) {
		p=++tott; ls[p] = ls[o]; rs[p] = rs[o]; sum[p] = sum[o]; return ;
	}
	if(!p) p = ++tott, sum[p] = sum[o];
	if(l==r) { sum[p] = sum[p] + x; return ; }
	int mid=(l+r)>>1;
	if(q<=mid) rs[p] = rs[o], modify(ls[o], ls[p], l, mid, q, x);
	else ls[p] = ls[o], modify(rs[o], rs[p], mid+1, r, q, x);
	pushup(p);
}
int query(int p, int l, int r, int ql, int qr) {
	if(l > qr || r < ql) return 0;
	if(ql <= l && r <= qr) return sum[p];
	int mid = (l+r>>1), resL = 0, resR = 0;
	if(ql <= mid) resL = query(ls[p], l, mid, ql, qr);
	if(qr > mid) resR = query(rs[p], mid+1, r, ql, qr);
	return resL + resR ;
}

pair< pir, pir > mods[__ << 1] ; int totc, rtL[_];

int main() {
	rd(n); f(i,1,n) rd(p[i]), pos[p[i]] = i; blocks.insert(make_tuple(n, 1, 0)); f(i,1,n) alter(pos[i]);
	for(auto v : tmp_ok) ok[++tot] = v;
	cerr << tot << endl;
	f(i,1,tot) {
		int l, m, r; tie(l, m, r) = ::ok[i];
		mods[++totc] = mp(mp(l, m+1), mp(r, 1));
		mods[++totc] = mp(mp(m+1, m+1), mp(r, -1));
	}
	f(i,1,n) mods[++totc] = mp(mp(i, 1), mp(n, 0));
	sort(mods+1, mods+totc+1);
	f(i,1,totc) {
		int tl=mods[i].fir.fir, l=mods[i].fir.sec, r=mods[i].sec.fir, x=mods[i].sec.sec;
		modify(rt[2*i-2], rt[2*i-1], 1, n, l, x);
		modify(rt[2*i-1], rt[2*i], 1, n, r+1, -x);
	}
	int p = 0;
	f(i,1,n) {
		while(p+1 <= totc && mods[p+1].fir.fir <= i) ++p;
		rtL[i] = rt[2*p];
	}
	rd(q); f(i,1,q) {
		int L = rd(), R = rd(), ok = 0;
		// f(x,1,tot) {
			// int l, m, r; tie(l, m, r) = ::ok[x];
			// [L, R] is ok when l <= L <= m < R <= r
			// if((l <= L) && (L <= m) && (m < R) && (R <= r)) ok = 1;
		// }
		ok = query(rtL[L], 1, n, 1, R);
		// cerr << ok << endl;
		cout << ( (ok>0) ? "YES" : "NO" ) << '\n';
		if(!(i%10)) cout.flush();
	}
	
	return 0;
}
≡