Description
我們常常會說這樣的話：“X年是自Y年以來降雨量最多的”。它的含義是X年的降雨量不超過Y年，且對于任意 Y＜Z＜X，Z年的降雨量嚴格小于X年。例如2002，2003，2004和2005年的降雨量分別為4920，5901，2832和3890， 則可以說“2005年是自2003年以來最多的”，但不能說“2005年是自2002年以來最多的”由于有些年份的降雨量未 知，有的說法是可能正確也可以不正確的。
Input
輸入僅一行包含一個正整數(shù)n，為已知的數(shù)據(jù)。以下n行每行兩個整數(shù)yi和ri，為年份和降雨量，按照年份從小 到大排列，即yi＜yi+1。下一行包含一個正整數(shù)m，為詢問的次數(shù)。以下m行每行包含兩個數(shù)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 Sample Output
false
true
false
maybe
false HINT
100%的數(shù)據(jù)滿足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9
代碼如下：
#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]){by_lmy新聞熱點
疑難解答
