新人求助，降雨量那题本机AC提交WAWAWA……
原题：
我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，
则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知，有的说法是可能正确也可以不正确的。
1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9
以前的博客说这题没啥思维难度，难就难在细节讨论
这次写信心爆棚认为老子现在问题处理地多棒，只需转化某些要点的表达方式就可以避免讨论
然后……
行吧，这次是我被练了
代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int oo=1000000007; 5 int n,a[51000],b[51000],m; 6 int v[210000]; bool u[210000]; 7 void gtsgmttr(int x,int l,int r){ 8 if(l==r){ 9 v[x]=b[l],u[x]=false; 10 return ; 11 } 12 int md=(l+r)>>1; 13 gtsgmttr(x<<1,l,md),gtsgmttr(x<<1|1,md+1,r); 14 v[x]=max(v[x<<1],v[x<<1|1]); 15 u[x]=(u[x<<1]|u[x<<1|1]|(a[md]+1!=a[md+1])); 16 } 17 int qrv(int x,int l,int r,int ql,int qr){ 18 if(l==ql && r==qr) return v[x]; 19 int md=(l+r)>>1; 20 if(ql<=md && qr>md) 21 return max(qrv(x<<1,l,md,ql,md),qrv(x<<1|1,md+1,r,md+1,qr)); 22 else if(qr<=md) return qrv(x<<1,l,md,ql,qr); 23 else return qrv(x<<1|1,md+1,r,ql,qr); 24 } 25 bool qru(int x,int l,int r,int ql,int qr){ 26 if(l==ql && r==qr) return u[x]; 27 int md=(l+r)>>1; 28 if(ql<=md && qr>md) 29 return (qru(x<<1,l,md,ql,md)|qru(x<<1|1,md+1,r,md+1,qr)|(a[md]+1!=a[md+1])); 30 else if(qr<=md) return qru(x<<1,l,md,ql,qr); 31 else return qru(x<<1|1,md+1,r,ql,qr); 32 } 33 int bnrsch(int x){ //如果找不到默认输出左侧的 34 int l=0,r=n,md; 35 //int l=1,r=n,md; 36 //如果l初值为1，则若左端点小于最小值，那么实际返回的是右侧的 37 while(l+1<r){ 38 md=(l+r)>>1; 39 (a[md]<x ? l : r)=md; 40 } 41 //return (a[l]!=x && a[r]!=x ? -1 : (a[l]==x ? l : r)); 42 return a[r]==x ? r : l; 43 } 44 int main(){ 45 freopen("ddd.in","r",stdin); 46 cin>>n; 47 for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]); 48 gtsgmttr(1,1,n); 49 cin>>m; 50 int l,r,x,y; 51 while(m --> 0){ 52 scanf("%d%d",&x,&y); 53 l=bnrsch(x),r=bnrsch(y); 54 if(x>=y+1) printf("false\n"); 55 //else if(a[r]!=y || a[l]!=x) printf("maybe\n"); 56 if(a[l]!=x && a[r]!=y) printf("maybe\n"); 57 else if(a[l]!=x || a[r]!=y){ 58 //注意如果两个端点只知道一个也是能判必错的 59 int tmp=(l+1<=r-(a[r]==y) ? qrv(1,1,n,l+1,r-(a[r]==y)) : 0); 60 if(a[l]!=x ? b[r]<=tmp : b[l]<=tmp) printf("false\n"); 61 else printf("maybe\n"); 62 } 63 else if(b[r]>b[l]) printf("false\n"); 64 else{ 65 int tmp=(l+1<=r-1 ? qrv(1,1,n,l+1,r-1) : 0); 66 if(b[r]<=tmp) printf("false\n"); 67 else if(qru(1,1,n,l,r)) printf("maybe\n"); 68 else printf("true\n"); 69 } 70 } 71 return 0; 72 }
原文：https://www.cnblogs.com/cdcq/p/12057643.html
