HYSBZ

1067: [SCOI2007]降雨量

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 6016 Solved: 1574
[Submit][Status][Discuss]

Description

　　我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，
则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知，有的说法是可能正确也可以不正确的。

Input

　　输入仅一行包含一个正整数n，为已知的数据。以下n行每行两个整数yi和ri，为年份和降雨量，按照年份从小
到大排列，即yi＜yi+1。下一行包含一个正整数m，为询问的次数。以下m行每行包含两个数Y和X，即询问“X年是
自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

　　对于每一个询问，输出true，false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

Source

POJ 2637 WorstWeather Ever

思路：线段树维护区间最小值，各种情况分类讨论一下就行了。

  1 #include <iostream>
  2 #include <fstream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <string>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <set>
 14 #include <map>
 15 #include <list>
 16 #include <iomanip>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <bitset>
 20 #include <ctime>
 21 
 22 using namespace std;
 23 
 24 #define pau system("pause")
 25 #define ll long long
 26 #define pii pair<int, int>
 27 #define pb push_back
 28 #define mp make_pair
 29 #define clr(a, x) memset(a, x, sizeof(a))
 30 
 31 const double pi = acos(-1.0);
 32 const int INF = 0x3f3f3f3f;
 33 const int MOD = 1e9 + 7;
 34 const double EPS = 1e-9;
 35 
 36 /*
 37 #include <ext/pb_ds/assoc_container.hpp>
 38 #include <ext/pb_ds/tree_policy.hpp>
 39 
 40 using namespace __gnu_pbds;
 41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T;
 42 */
 43 
 44 int n, q;
 45 struct gg {
 46     int y, r;
 47     gg () {}
 48     gg (int y, int r) : y(y), r(r) {}
 49     bool operator < (const gg &g) const {
 50         return y == g.y ? r < g.r : y < g.y;}
 51 } g[50015];
 52 int ma[200015];
 53 void pushup(int i) {
 54     ma[i] = max(ma[i << 1], ma[i << 1 | 1]);
 55 }
 56 void build(int i, int l, int r) {
 57     if (l == r) {
 58         ma[i] = g[l].r;
 59         return;
 60     }
 61     int mi = l + r >> 1;
 62     build(i << 1, l, mi);
 63     build(i << 1 | 1, mi + 1, r);
 64     pushup(i);
 65 }
 66 int query(int i, int l, int r, int x, int y) {
 67     if (x > y) return 0;
 68     if (x <= l && r <= y) {
 69         return ma[i];
 70     }
 71     int mi = l + r >> 1, res1 = -MOD, res2 = -MOD;
 72     if (x <= mi) res1 = query(i << 1, l, mi, x, y);
 73     if (mi < y) res2 = query(i << 1 | 1, mi + 1, r, x, y);
 74     return max(res1, res2);
 75 }
 76 int main() {
 77     scanf("%d", &n);
 78     for (int i = 1; i <= n; ++i) {
 79         scanf("%d%d", &g[i].y, &g[i].r);
 80     }
 81     build(1, 1, n);
 82     scanf("%d", &q);
 83     while (q--) {
 84         int x, y;
 85         scanf("%d%d", &x, &y);
 86         int p2 = lower_bound(g + 1, g + n + 1, gg(y, 0)) - g;
 87         int p1 = lower_bound(g + 1, g + n + 1, gg(x, 0)) - g;
 88         if (g[p2].y != y) {
 89             if (g[p1].y != x) {
 90                 puts("maybe");
 91             } else {
 92                 int tma = query(1, 1, n, p1 + 1, p2 - 1);
 93                 if (tma >= g[p1].r) {
 94                     puts("false");
 95                 } else {
 96                     puts("maybe");
 97                 }
 98             }
 99         } else {
100             if (g[p1].y == x) {
101                 int tma = query(1, 1, n, p1 + 1, p2 - 1);
102                 if (tma >= g[p2].r || g[p1].r < g[p2].r) {
103                     puts("false");
104                 } else if (p2 - p1 == y - x) {
105                     puts("true");
106                 } else {
107                     puts("maybe");
108                 }
109             } else {
110                 int tma = query(1, 1, n, p1, p2 - 1);
111                 if (tma >= g[p2].r) {
112                     puts("false");
113                 } else {
114                     puts("maybe");
115                 }
116             }
117         }
118     }
119     return 0;
120 }