1067: [SCOI2007]降雨量
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3004 Solved: 767
[Submit][Status][Discuss]
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
Source
首先，妈妈我要报警了，WA了N次，WA一次改一次，主要是分类讨论的问题，所谓谋而后动，根据每个错误点针对性的改错并不能治本，编了一下午，结果晚上不到30min，重新理清思路编了一遍直接A了，思路才是一次编程的核心，思路对了，才为AC奠定基础。但我还是要报警nmb。
ps：心狠累。。具体不写了。。程序清楚明了。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define N 50000
using namespace std;
struct data{int mx,lx,rx,k;}seg[N*];
int n,m,lb,fb,hb,px,py,maxn,ct;
int know[N],a[N],rain[N];
void updata(int now)
{
seg[now].mx=max(seg[(now<<)].mx,seg[(now<<)+].mx);
seg[now].k=seg[(now<<)].k|seg[(now<<)+].k;
}
void buildtree(int now,int l,int r)
{
seg[now].lx=l; seg[now].rx=r;
if (l==r) {seg[now].mx=rain[l]; seg[now].k=know[l]; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
updata(now);
}
int query(int now,int begin,int end)
{
int l=seg[now].lx,r=seg[now].rx;
if (begin<=l && end>=r) {hb=hb|seg[now].k; return seg[now].mx;}
int mid=(l+r)>>,ans=;
if (begin<=mid) ans=max(query((now<<),begin,end),ans);
if (end>mid) ans=max(query((now<<)+,begin,end),ans);
return ans;
}
int main()
{
int i;
int x,y;
scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d%d",&a[i],&rain[i]);
if (a[i]-a[i-]!=&&i!=) know[i]=;
}
buildtree(,,n);
scanf("%d",&m);
for (i=;i<=m;i++)
{
fb=; hb=; lb=;
scanf("%d%d",&x,&y);
if (x>=y) {printf("false\n"); continue;}
if (y<=a[]||x>=a[n]) {printf("maybe\n");continue;}
px=lower_bound(a+,a+n+,x)-a; py=lower_bound(a+,a+n+,y)-a;
if (a[px]!=x) fb=; if (a[py]!=y) lb=;
if (fb&&lb) {printf("maybe\n");continue;}
if (!fb)
if (a[px+]-a[px]!=) hb=;
if (!lb)
if (a[py]-a[py-]!=) hb=;
if (fb&&lb) maxn=query(,px,py-);
else if (!fb&&lb) maxn=query(,px+,py-);
else if (fb&&!lb) maxn=query(,px,py-);
else if (!fb&&!lb) maxn=query(,px+,py-);
if (!fb&&!lb&&!hb&&rain[px]>=rain[py]&&maxn<rain[py]) {printf("true\n");continue;}
if (!fb&&!lb&&hb&&rain[px]>=rain[py]&&maxn<rain[py]) {printf("maybe\n");continue;}
if (!fb&&lb&&maxn<rain[px]) {printf("maybe\n"); continue;}
if (fb&&!lb&&maxn<rain[py]) {printf("maybe\n"); continue;}
printf("false\n");
}
return ;
}
BZOJ版
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 50000
using namespace std;
struct data{int mx,lx,rx,k;}seg[N*];
int n,m,lb,fb,hb,px,py,maxn,T;
int know[N],a[N],rain[N];
void updata(int now)
{
seg[now].mx=max(seg[(now<<)].mx,seg[(now<<)+].mx);
seg[now].k=seg[(now<<)].k|seg[(now<<)+].k;
}
void buildtree(int now,int l,int r)
{
seg[now].lx=l; seg[now].rx=r;
if (l==r) {seg[now].mx=rain[l]; seg[now].k=know[l]; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
updata(now);
}
int query(int now,int begin,int end)
{
int l=seg[now].lx,r=seg[now].rx;
if (begin<=l && end>=r) {hb=hb|seg[now].k; return seg[now].mx;}
int mid=(l+r)>>,ans=;
if (begin<=mid) ans=max(query((now<<),begin,end),ans);
if (end>mid) ans=max(query((now<<)+,begin,end),ans);
return ans;
}
int main()
{
int i;
int x,y;
while (~scanf("%d",&n))
{
if (n==) break;
memset(seg,,sizeof(seg));
memset(rain,,sizeof(rain));
memset(know,,sizeof(know));
memset(a,,sizeof(a));
for (i=;i<=n;i++)
{
scanf("%d%d",&a[i],&rain[i]);
if (a[i]-a[i-]!=&&i!=) know[i]=;
}
buildtree(,,n);
scanf("%d",&m);
for (i=;i<=m;i++)
{
fb=; hb=; lb=;
scanf("%d%d",&x,&y);
if (x>=y) {printf("false\n"); continue;}
if (y<=a[]||x>=a[n]) {printf("maybe\n");continue;}
px=lower_bound(a+,a+n+,x)-a; py=lower_bound(a+,a+n+,y)-a;
if (a[px]!=x) fb=; if (a[py]!=y) lb=;
if (fb&&lb) {printf("maybe\n");continue;}
if (!fb)
if (a[px+]-a[px]!=) hb=;
if (!lb)
if (a[py]-a[py-]!=) hb=;
if (fb&&lb) maxn=query(,px,py-);
else if (!fb&&lb) maxn=query(,px+,py-);
else if (fb&&!lb) maxn=query(,px,py-);
else if (!fb&&!lb) maxn=query(,px+,py-);
if (!fb&&!lb&&!hb&&rain[px]>=rain[py]&&maxn<rain[py]) {printf("true\n");continue;}
if (!fb&&!lb&&hb&&rain[px]>=rain[py]&&maxn<rain[py]) {printf("maybe\n");continue;}
if (!fb&&lb&&maxn<rain[px]) {printf("maybe\n"); continue;}
if (fb&&!lb&&maxn<rain[py]) {printf("maybe\n"); continue;}
printf("false\n");
}
printf("\n");
}
return ;
}
POJ版（多组数据）