codevs 2439 降雨量 （RMQ+离散化+令人窒息的分类讨论）

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

对于每一个询问，输出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

数据范围及提示 Data Size & Hint

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

借鉴了一大佬的博客  http://www.cnblogs.com/CQzhangyu/p/6878335.html

分析：首先先离散化处理数据，然后开始令人窒息的分类讨论

true的条件很严苛，只有当左右端点已知，且左端点大于等于右端点的值，中间年份最大值已知，且小于右端点的值，且年份连续

maybe的条件有很多

1：左右端点都不知 2：左端点已知，右端点未知，中间最大值小于左端点值 3：右端点已知，左端点未知，中间最大值小于右端点值 4：中间最大值未知，左端点值大于右端点值 :5：只有当左右端点已知，且左端点大于等于右端点的值，中间年份最大值已知，且小于右端点的值，但年份不连续

false的条件有1：左端点年份大于等于右端点年份 2：以上的其他都为false

对于这题一定要细心！！！

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define MAX_N 70005 #define INF 1000000005 using namespace std; int dp[MAX_N][20],q[10005][2],s[MAX_N],vis[MAX_N]; struct node { int y,k,org; }a[MAX_N]; bool cmp(node a, node b) { return a.y<b.y; } int main() { int n,m,cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].k); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d%d",&a[n+2*i-1].y,&a[n+2*i].y),a[n+2*i-1].org=a[n+2*i].org=i,a[n+2*i].k=1,a[n+2*i-1].k=0; sort(a+1,a+1+n+2*m,cmp); vis[0]=-INF,s[0]=0; for(int i=1;i<=n+2*m;i++) { if(a[i].y>vis[cnt]) vis[++cnt]=a[i].y,s[cnt]=s[cnt-1]; if(a[i].org) q[a[i].org][a[i].k]=cnt; else dp[cnt][0]=a[i].k,s[cnt]++; } for(int j=1;(1<<j)<=cnt;j++) for(int i=1;i+(1<<j)-1<=cnt;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); for(int i=1;i<=m;i++) { int ql=q[i][0],qr=q[i][1],maxn,flag=0,len=qr-ql-1; int k=log2(len); if(ql+1>qr-1) maxn=0; else maxn=max(dp[ql+1][k],dp[qr-(1<<k)][k]); if(vis[qr]-vis[ql]==s[qr]-s[ql]) flag=1; if(ql>=qr) printf("false\n"); else if(dp[ql][0]&&dp[qr][0]&&flag&&dp[ql][0]>=dp[qr][0]&&maxn<dp[qr][0]) printf("true\n"); else if(!dp[ql][0]&&!dp[qr][0]) printf("maybe\n"); else if(dp[ql][0]&&!dp[qr][0]&&maxn<dp[ql][0]) printf("maybe\n"); else if(!dp[ql][0]&&dp[qr][0]&&maxn<dp[qr][0]) printf("maybe\n"); else if(!maxn&&dp[ql][0]>=dp[qr][0]) printf("maybe\n"); else if(dp[ql][0]&&dp[qr][0]&&maxn<dp[qr][0]&&dp[ql][0]>=dp[qr][0]&&!flag) printf("maybe\n"); else printf("false\n"); } return 0; }