BZOJ1067[SCOI2007]降雨量

2019-11-09 19:49:40

字體：大中小

供稿：網(wǎng)友

Description

　　我們常常會(huì)說(shuō)這樣的話(huà)：“X年是自Y年以來(lái)降雨量最多的”。它的含義是X年的降雨量不超過(guò)Y年，且對(duì)于任意 Y＜Z＜X，Z年的降雨量嚴(yán)格小于X年。例如2002，2003，2004和2005年的降雨量分別為4920，5901，2832和3890，則可以說(shuō)“2005年是自2003年以來(lái)最多的”，但不能說(shuō)“2005年是自2002年以來(lái)最多的”由于有些年份的降雨量未知，有的說(shuō)法是可能正確也可以不正確的。

Input

　　輸入僅一行包含一個(gè)正整數(shù)n，為已知的數(shù)據(jù)。以下n行每行兩個(gè)整數(shù)yi和ri，為年份和降雨量，按照年份從小到大排列，即yi＜yi+1。下一行包含一個(gè)正整數(shù)m，為詢(xún)問(wèn)的次數(shù)。以下m行每行包含兩個(gè)數(shù)Y和X，即詢(xún)問(wèn)“X年是自Y年以來(lái)降雨量最多的。”這句話(huà)是必真、必假還是“有可能”。

Output

　　對(duì)于每一個(gè)詢(xún)問(wèn)，輸出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%的數(shù)據(jù)滿(mǎn)足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

這道題TM卡了我整整5個(gè)小時(shí)！！！

誰(shuí)讓我手賤選了一道賊賤的題

大家想一想，怎樣才能輸出true呢

true：（全部滿(mǎn)足）

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

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

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

false：（滿(mǎn)足下列一個(gè)條件即可）

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

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

maybe就是剩下的了

利用這些條件，可以用線(xiàn)段樹(shù)解決。（不知道線(xiàn)段樹(shù)是神馬的童鞋看我博客~~）

代碼如下：

#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;//找第一個(gè)大于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])//如果滿(mǎn)足上面我說(shuō)的條件 { if(t1==t2)//坑了我好久 { if(r[t1-1]>=r[t2]){by_lmy