题解 P2471 【[SCOI2007]降雨量】

有一种打法叫做暴力讨论美学 首先你根据$Z,X,Y$是否确定记录$bool$值$fx,fy,fz$，显然$fx,fy,fz$总共就$8$种情况，全部讨论一遍就行了233333 虽然代码比较长但是这样是最不需要动脑子的 ```cpp #include<bits/stdc++.h> #define fo(i, a, b) for(int i = (a); i <= (b); ++i) #define N 100005 #define inf 1000000005 #define ls t[u].s[0] #define rs t[u].s[1] #define pb push_back int A, B, Q, n, m, cnt; std::map<int, int> mp; struct node{ int max, sum, s[2]; friend node operator + (node x, node y) { return (node) {std::max(x.max, y.max), x.sum + y.sum}; } }t[N << 2]; inline void modify (int &u, int L, int R, int pos, int val) { if (!u) u = ++cnt; if (L == R) { t[u].sum = 1; t[u].max = val; return; } int mid = L + R >> 1; if (pos <= mid) modify(ls, L, mid, pos, val); else modify(rs, mid + 1, R, pos, val); t[u].max = std::max(t[ls].max, t[rs].max); t[u].sum = t[ls].sum + t[rs].sum; } inline node query (int u, int L, int R, int l, int r) { node ret = (node) {-inf, 0}; if (!u) return ret; if (l <= L && R <= r) { return t[u]; } int mid = L + R >> 1; if (l <= mid) {ret = ret + query(ls, L, mid, l, r);} if (mid < r) {ret = ret + query(rs, mid + 1, R, l, r);} return ret; } int main () { int T; scanf("%d", &n); fo (i, 1, 4 * n) t[i].max = -inf; int rt = 0; fo (i, 1, n) { int x, y; scanf("%d %d", &x, &y); mp[x] = y; modify(rt, -inf, inf, x, y); } scanf("%d", &Q); while (Q--) { int x, y, vx = -inf, vy = -inf; bool fx = 0, fy = 0, fz = 0; scanf("%d %d", &y, &x); if (mp.find(x) != mp.end()) { vx = mp[x]; fx = 1; } if (mp.find(y) != mp.end()) { vy = mp[y]; fy = 1; } if (x + 1 == y) { if (fx && fy) { if (vx <= vy) printf("true\n"); else printf("false\n"); } else printf("maybe\n"); continue; } --x; ++y; node ans = (node) {-inf, 0}; int now = 0; if (y <= x) ans = query(1, -inf, inf, y, x); if (ans.sum == x - y + 1) fz = 1; int vz = ans.max; if (!fz && !fx && !fy) { printf("maybe\n"); continue; } if (fz && !fx && !fy) { printf("maybe\n"); continue; } if (!fz && fx && !fy) { if (vz >= vx) printf("false\n"); else printf("maybe\n"); continue; } if (!fz && !fx && fy) { if (vz >= vy) printf("false\n"); else printf("maybe\n"); continue; } if (fz && fx && !fy) { if (vz >= vx) printf("false\n"); else printf("maybe\n"); continue; } if (fz && !fx && fy) { if (vz >= vy) printf("false\n"); else printf("maybe\n"); continue; } if (!fz && fx && fy) { if (vx > vy) { printf("false\n"); continue; } if (vx <= vz) { printf("false\n"); continue; } printf("maybe\n"); continue; } if (fz && fx && fy) { if (vy >= vx && vx > vz) { printf("true\n"); } else { printf("false\n"); } } } return 0; } ```