[SCOI 2007] 降雨量

题目大意

给出 nn 条数据表示 yiy_i 年的降雨量为 nin_i ,保证有 yiy_i 单调递增。

我们能说「xx 是自 yy 年以来降雨量最多的一年」当且仅当:

  • nxnyn_x \leqslant n_y
  • ni<nx  (y<i<x)n_i < n_x \; (y < i < x)

给出 mm 组询问,询问 xx 是否能称作「自 yy 年以来降雨量最多的一年」。输出 true 表示一定能、false 表示一定不能、maybe 表示可能能。

1n50,0001 \leqslant n \leqslant 50,000

1m10,0001 \leqslant m \leqslant 10,000

1ni1,000,000,0001 \leqslant n_i \leqslant 1,000,000,000

1,000,000,000yi1,000,000,000-1,000,000,000 \leqslant y_i \leqslant 1,000,000,000

题目链接

【SCOI 2007】降雨量 - Luogu 2471

题解

BZOJ 的评论区好像有经典的一楼啊。。。

线段树 + 各种分类。

如果询问的年份及之间的年份的数据都已知,那么可以通过之间的最大值判断是「一定能」还是「一定不能」。

如果两头都未知,那么「可能」。

如果一端已知,通过中间的最大值判断是「可能」还是「一定不能」。

代码

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
#include <cstdio>
#include <algorithm>
struct SegT {
struct Node {
Node *lc, *rc;
int ly, ry, max;
bool known;
Node(Node *lc, Node *rc) : lc(lc), rc(rc), known(true) {}
int query(int l, int r, int num) {
if (l <= ly && ry <= r) {
if (max >= num) return 0;
return known ? 1 : 2;
}
if (r <= lc->ry) return lc->query(l, r, num);
if (l >= rc->ly) return rc->query(l, r, num);
if (lc->ry < l && r < rc->ly) return 2;
int ql = lc->query(l, r, num), qr = rc->query(l, r, num);
if (!ql || !qr) return 0;
if (lc->ry + 1 < rc->ly) return 2;
else return 1;
}
int query(int y) {
if (ly == ry) return y == ly ? max : 0;
if (y <= lc->ry) return lc->query(y);
if (y >= rc->ly) return rc->query(y);
return 0;
}
int queryNext(int y) {
if (ly == ry) return ly;
if (y < lc->ry) return lc->queryNext(y);
else return rc->queryNext(y);
}
int queryLast(int y) {
if (ly == ry) return ly;
if (y > rc->ly) return rc->queryLast(y);
else return lc->queryLast(y);
}
} *root;
SegT() : root(NULL) {}
Node *build(int l, int r) {
if (l == r) {
Node *u = new Node(NULL, NULL);
scanf("%d %d", &u->ly, &u->max);
u->ry = u->ly;
return u;
}
int mid = l + (r - l) / 2;
Node *u = new Node(build(l, mid), build(mid + 1, r));
u->max = std::max(u->lc->max, u->rc->max);
u->known = u->lc->known && u->rc->known;
if (u->lc->ry + 1 < u->rc->ly) u->known = false;
u->ly = u->lc->ly;
u->ry = u->rc->ry;
return u;
}
int query(int l, int r, int num) {
return root->query(l, r, num);
}
int query(int y) {
return root->query(y);
}
int queryNext(int y) {
return root->queryNext(y);
}
int queryLast(int y) {
return root->queryLast(y);
}
} segT;
int main() {
int n;
scanf("%d", &n);
segT.root = segT.build(1, n);
int m;
scanf("%d", &m);
while (m--) {
int l, r;
scanf("%d %d", &l, &r);
if (l > r) {
puts("false");
continue;
}
if (l == r) {
puts("true");
continue;
}
int lNum = segT.query(l), rNum = segT.query(r);
if (!lNum && !rNum) {
puts("maybe");
continue;
}
int s = segT.queryNext(l), t = segT.queryLast(r);
if (!lNum) {
if (s > t || t == r) {
puts("maybe");
continue;
}
puts(segT.query(s, t, rNum) ? "maybe" : "false");
continue;
}
if (!rNum) {
if (s > t || s == l) {
puts("maybe");
continue;
}
puts(segT.query(s, t, lNum) ? "maybe" : "false");
continue;
}
if (rNum > lNum) {
puts("false");
continue;
}
if (s > t) {
puts(l + 1 == r ? "true" : "maybe");
continue;
}
int temp = segT.query(s, t, rNum);
if (!temp) puts("false");
else if (temp == 1) puts(l + 1 == s && t + 1 == r ? "true" : "maybe");
else puts("maybe");
}
return 0;
}