BZOJ1067[SCOI2007]降雨量

2019-11-10 17:32:53

字体：大中小

来源：转载

供稿：网友

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

2002 2005

2003 2005

2002 2007

2003 2007

2005 2008 Sample Output

false

true

false

maybe

false HINT

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

这道题TM卡了我整整5个小时！！！

谁让我手贱选了一道贼贱的题

大家想一想，怎样才能输出true呢

true：（全部满足）

1.x年的降雨量小于等于y年的降雨量

2.x年的降雨量大于y+1~x-1的最大降雨量

3.y~x年的降雨量全部给出

false：（满足下列一个条件即可）

1.x年的降雨量大于y年的降雨量

2.x年的降雨量小于等于于y+1~x-1的最大降雨量

maybe就是剩下的了

利用这些条件，可以用线段树解决。（不知道线段树是神马的童鞋看我博客~~）

代码如下：

#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;int n,m;int y[1100000],r[1100000];struct node{ int l,r,lc,rc,c;}tr[2100000];int trlen;void bt(int ll,int rr){ int now=++trlen; tr[now].l=ll;tr[now].r=rr;tr[now].c=-0x7fff; tr[now].lc=tr[now].rc=-0x7fff; if(ll==rr)tr[now].c=r[ll]; if(ll<rr) { int mid=(ll+rr)/2; tr[now].lc=trlen+1;bt(ll,mid); tr[now].rc=trlen+1;bt(mid+1,rr); tr[now].c=max(tr[tr[now].lc].c,tr[tr[now].rc].c); }}int findmax(int now,int l,int r){ if(tr[now].l==l&&tr[now].r==r)return tr[now].c; int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(mid+1<=l)return findmax(rc,l,r); else if(r<=mid)return findmax(lc,l,r); else return max(findmax(lc,l,mid),findmax(rc,mid+1,r));}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&y[i],&r[i]); trlen=0;bt(1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { int xx,yy,t1,t2; scanf("%d%d",&xx,&yy);//我这里的xx，yy反了，大家注意 t1=upper_bound(y+1,y+n+1,xx)-y;//找第一个大于xx的年份的位置 t2=lower_bound(y+1,y+n+1,yy)-y;//找yy的年份的位置 if (y[t2]==yy&&y[t1-1]==xx&&t1!=n+1&&t2!=n+1&&t2-t1==yy-xx-1&&r[t2]<=r[t1-1])//如果满足上面我说的条件 { if(t1==t2)//坑了我好久 { if(r[t1-1]>=r[t2]){PRintf("true/n");continue;}//如果两个年份挨在一起，直接看第一个条件 else{printf("false/n");continue;} } else { if(findmax(1,t1,t2-1)<r[t2]){printf("true/n");continue;}//线段树~ else{printf("false/n");continue;} } } if(y[t2]==yy&&y[t1-1]==xx&&r[t2]>r[t1-1]){printf("false/n");continue;}//第一个条件不满足 if(t2==t1){printf("maybe/n");continue;}//年份一样，说明中间有年份未知 if(y[t2]==yy&&t2!=n+1)if(findmax(1,t1,t2-1)>=r[t2]){printf("false/n");continue;}//最大值不是yy年，第二个条件不对 if(y[t1-1]==xx&&t1!=n+1)if(findmax(1,t1,t2-1)>=r[t1-1]){printf("false/n");continue;}//如果xx~yy的最大值不是xx年的，那么绝对错误，自己看第一个条件。 printf("maybe/n");//省下的都是maybe } return 0;}

by_lmy

上一篇：寒假训练赛（七）自我总结

下一篇：JVM：如何分析线程堆栈