首页 > 代码库 > bzoj1067 scoi2007 降雨量 RMQ+讨论
bzoj1067 scoi2007 降雨量 RMQ+讨论
很水的题目
滚回来之后的第一道题
竟然做了1个多小时
最近的状态极其不好,这样下去有可能省队都进不了。。。
这个题算是RMQ的基础题了
写他就是为了练习RMQ的
首先预处理出来区间Max
我们注意到10^9的区间显然太大了,但是其中有用的点非常少,所以我们要离散出来
当然题目中其实已经给你排好序了。。。
所以在st 表建好以后,就每次读入然后二分找对应的离散后的相应坐标,然后o(1)就可以完成询问
具体的情况比较多
不过都听好想的
如果wa了看代码吧
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define MAX 50009 #define rep(i, j, k) for(int i = j; i <= k; i++) using namespace std; int n, m, f[MAX][50]; int a[MAX], b[MAX]; inline int ask (int l, int r) { if (l > r) return -0x7fffffff; int t = 0; while (1 << (t + 1) <= r - l + 1) t++; return max (f[l][t], f[r - (1 << t) + 1][t]); } int main() { scanf ("%d", &n); rep (i, 1, n) scanf ("%d%d", &a[i], &b[i]); rep (i, 1, n) f[i][0] = b[i]; for (int j = 1; (1 << j) <= n; j++) for (int i = 1; i + (1<<j) - 1 <= n; i ++) f[i][j] = max (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); scanf ("%d", &m); while (m--) { int a1, a2, l, r; scanf ("%d%d", &a1, &a2); l = lower_bound (a + 1, a + 1 + n, a1) - a; r = lower_bound (a + 1, a + 1 + n, a2) - a; int full = (a2 - a1 +1 == r - l + 1); if (a[r] != a2 && a[l] != a1) { printf ("maybe\n"); continue; } if (a[r] != a2) { int Max = ask (l + 1, r - 1); if (Max <= b[l])//or < ?? printf ("maybe\n"); else printf ("false\n"); continue; } if (a[l] != a1) { int Max = ask (l, r - 1); if (b[r] > Max) printf ("maybe\n"); else printf ("false\n"); continue; } if (b[r] > b[l]) { printf ("false\n"); continue; } if (full) { int Max = ask (l + 1, r - 1); if (Max < b[r] && b[r] <= b[l]) printf ("true\n"); else printf ("false\n"); continue; } else { int Max = ask (l + 1, r - 1); if (Max < b[r] && b[r] <= b[l]) printf ("maybe\n"); else printf ("false\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。