http://www.lydsy.com/JudgeOnline/problem.php?id=1067
好不爽，弄了一个晚上。
好不爽。
还是照着别人程序拍着看的！！！
噗
这题很变态。
首先，我没看清楚题，以为是严格上升！！！！！！所以误导了我。
然后这题的判定非常hentai！！
我们来考虑true的情况【x年到y年】：
- x已知并且y已知
- y年降水量不超过x年
- x+1到y-1年已知并且都小于y年降水量
然后是maybe的情况【x年到y年】：
- x已知并且y已知
- y年降水量不超过x年
- x+1到y-1年至少有一年未知并且已知的都小于y年降水量
或
- x已知或y已知
- 若x已知，那么x+1到y年至少有一年未知并且已知的都小于x年降水量
- 若y已知，那么x到y-1年至少有一年未知并且已知的都小于y年降水量
最后是false的情况，如果不是以上两种情况，就是false
很变态！
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=100005, M=10005;
int d[N][20], a[N], w[N], n, o; void st() {
for1(i, 1, n) d[i][0]=w[i];
for(int j=1; (1<<j)<=n; ++j)
for(int i=1; i+(1<<(j-1))<=n; ++i)
d[i][j]=max(d[i][j-1], d[i+(1<<(j-1))][j-1]);
}
inline const int getmax(const int &l, const int &r) {
if(l>r) return -2000000000;
int s=r-l+1, k=0;
while((1<<(k+1))<=s) ++k;
return max(d[l][k], d[r-(1<<k)+1][k]);
}
inline int getpos(const int &x) {
return lower_bound(a+1, a+1+n, x)-a;
} int main() {
read(n);
for1(i, 1, n) { read(a[i]); read(w[i]); }
read(o);
st();
int x, y, m, r, l, ans;
for1(i, 1, o) {
read(x); read(y);
l=getpos(x), r=getpos(y);
bool nl=(l<=n && a[l]==x), nr=(r<=n && a[r]==y);
if(nl) {
if(nr) { //true条件1，maybe第一种情况的条件1
m=getmax(l+1, r-1);
if(w[l]<w[r]) ans=0; //true条件2，maybe第一种情况的条件2
else if(m<w[r]) { //true条件3
if(r-l==y-x) ans=1; //true条件3
else ans=-1; //maybe第一种情况的条件3
}
else ans=0;
}
else {
m=getmax(l+1, r-1); //这里要注意，因为getpos是开区间，会飙到外边，所以是r-1
if(m<w[l]) ans=-1; //maybe第二种情况的条件2
else ans=0;
}
}
else {
if(nr) {
m=getmax(l, r-1);
if(m<w[r]) ans=-1;
else ans=0;
}
else ans=-1;
}
if(ans==1) puts("true");
else if(ans==-1) puts("maybe");
else puts("false");
}
return 0;
}
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
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
true
false
maybe
false
HINT
100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9