BZOJ1067 [SCOI2007]降雨量 RMQ???
求救!!!神犇帮我瞅瞅呗。。。未完。。。调了2个半小时线段树,没调出来,大家帮帮我啊!!!
小詹用st表写。
我的思路就是把中间空着的年份设为无限,然后一点点特判就行了。。。然而没出来。。。
[SCOI2007]降雨量
题干:
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
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
true
false
maybe
false
HINT
100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9
我的凉凉线段树代码:
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } int z = 0,n,len = 0; int rain[50005],pl[50005],ans = 0; int tree[200005],name[200005]; void build(int o,int l,int r) { if(l == r) { tree[o] = rain[l]; name[o] = l; return; } int mid = (l + r) >> 1; build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r); if(tree[o << 1] > tree[o << 1 | 1]) { tree[o] = tree[o << 1]; name[o] = name[o << 1]; } else if(tree[o << 1] < tree[o << 1 | 1]) { tree[o] = tree[o << 1 | 1]; name[o] = name[o << 1 | 1]; } else { tree[o] = INF; // name[o] = 0; } } int query(int o,int l,int r,int x,int y) { cout<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<o<<endl; if(l == x && r == y) { ans = name[o]; cout<<tree[o]<<endl; if(tree[o] == INF) { if(l != r) { int mid = (l + r) / 2; return max(query(o * 2,l,mid,l,mid),query(o * 2,mid + 1,r,mid + 1,r)); } else return -333; } return tree[o]; } int mid = (l + r) >> 1; if(y <= mid) { return query(o * 2,l,mid,x,y); } else if(mid < x) return query(o * 2 + 1,mid + 1,r,x,y); else { return max(query(o * 2,l,mid,x,mid),query(o * 2 + 1,mid + 1,r,mid + 1,y)); } } int judge(int l,int r) { z = 0; int x = query(1,1,len,l + 1,r); cout<<x<<endl; if(x == rain[r] && z == 1) return 2; else if(x == rain[r]) return 1; else return 3; } int main() { read(n); int x,y; duke(i,1,n) { read(x);read(y); if(pl[len] != x - 1 && i != 1) { int k = pl[len]; pl[++len] = k + 1; rain[len] = INF; // cout<<len<<" "<<rain[len]<<endl; } pl[++len] = x; rain[len] = y; } build(1,1,len); // printf("%d %d\n",tree[1],name[1]); int m; read(m); duke(i,1,m) { read(x);read(y); int p = lower_bound(pl + 1,pl + len + 1,x) - pl; int q = lower_bound(pl + 1,pl + len + 1,y) - pl; cout<<p<<" "<<q<<endl; int t = judge(p,q); if(t == 1) { printf("true\n"); } else if(t == 2) { printf("maybe\n"); } else { printf("false\n"); } } return 0; } /* 6 2002 4920 2003 5901 2004 2832 2005 3890 2007 5609 2008 3024 5 2002 2005 2003 2005 2002 2007 2003 2007 2005 2008 */ /* 6 2002 4920 2003 5901 2004 2832 2005 3890 2007 5609 2008 3024 2 2002 2007 2003 2007 */
小詹的st表算法:
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdlib> #include<stack> #include<queue> #include<vector> #include<cctype> using namespace std; #define space putchar(' ') #define enter puts("") #define Mem(a) memset(a, 0, sizeof(a)) typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 5e4 + 5; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) {last = ch; ch = getchar();} while(isdigit(ch)) {ans = (ans << 3) + (ans << 1) + ch - '0'; ch = getchar();} if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } int n, m, a[maxn], yr[maxn]; int dp[maxn][25], b[maxn]; void rmq() { for(int i = 1; i <= n; ++i) dp[i][0] = a[i]; for(int j = 1; (1 << j) <= n; ++j) for(int i = 1; i + (1 << j) - 1 <= n; ++i) dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); int x = 0; for(int i = 1; i <= n; ++i) { b[i] = x; if((1 << (x + 1)) <= i + 1) x++; } } int query(int L, int R) { int k = b[R - L + 1]; return max(dp[L][k], dp[R - (1 << k) + 1][k]); } int main() { n = read(); for(int i = 1; i <= n; ++i) yr[i] = read(), a[i] = read(); rmq(); m = read(); for(int i = 1; i <= m; ++i) { int y = read(), x = read(); if(x <= y) printf("false\n"); else { int L = lower_bound(yr + 1, yr + n + 1, y) - yr; int R = lower_bound(yr + 1, yr + n + 1, x) - yr; bool fl = yr[L] == y, fr = yr[R] == x; int ans = 0; if(L + (fl ? 1 : 0) <= R - 1) ans = query(L + (fl ? 1 : 0), R - 1); //别忘了这个判断啊…… if((fr && ans >= a[R]) || (fl && ans >= a[L]) || (fl && fr && (a[L] < a[R] || ans >= a[R]))) printf("false\n"); else if(R - L != yr[R] - yr[L] || !fl || !fr) printf("maybe\n"); else printf("true\n"); } } return 0; }