新人求助,降雨量那题本机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
以前的博客说这题没啥思维难度,难就难在细节讨论
这次写信心爆棚认为老子现在问题处理地多棒,只需转化某些要点的表达方式就可以避免讨论
然后……
行吧,这次是我被练了
代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int oo=;
int n,a[],b[],m;
int v[]; bool u[];
void gtsgmttr(int x,int l,int r){
if(l==r){
v[x]=b[l],u[x]=false;
return ;
}
int md=(l+r)>>;
gtsgmttr(x<<,l,md),gtsgmttr(x<<|,md+,r);
v[x]=max(v[x<<],v[x<<|]);
u[x]=(u[x<<]|u[x<<|]|(a[md]+!=a[md+]));
}
int qrv(int x,int l,int r,int ql,int qr){
if(l==ql && r==qr) return v[x];
int md=(l+r)>>;
if(ql<=md && qr>md)
return max(qrv(x<<,l,md,ql,md),qrv(x<<|,md+,r,md+,qr));
else if(qr<=md) return qrv(x<<,l,md,ql,qr);
else return qrv(x<<|,md+,r,ql,qr);
}
bool qru(int x,int l,int r,int ql,int qr){
if(l==ql && r==qr) return u[x];
int md=(l+r)>>;
if(ql<=md && qr>md)
return (qru(x<<,l,md,ql,md)|qru(x<<|,md+,r,md+,qr)|(a[md]+!=a[md+]));
else if(qr<=md) return qru(x<<,l,md,ql,qr);
else return qru(x<<|,md+,r,ql,qr);
}
int bnrsch(int x){ //如果找不到默认输出左侧的
int l=,r=n,md;
//int l=1,r=n,md;
//如果l初值为1,则若左端点小于最小值,那么实际返回的是右侧的
while(l+<r){
md=(l+r)>>;
(a[md]<x ? l : r)=md;
}
//return (a[l]!=x && a[r]!=x ? -1 : (a[l]==x ? l : r));
return a[r]==x ? r : l;
}
int main(){
freopen("ddd.in","r",stdin);
cin>>n;
for(int i=;i<=n;++i) scanf("%d%d",&a[i],&b[i]);
gtsgmttr(,,n);
cin>>m;
int l,r,x,y;
while(m --> ){
scanf("%d%d",&x,&y);
l=bnrsch(x),r=bnrsch(y);
if(x>=y+) printf("false\n");
//else if(a[r]!=y || a[l]!=x) printf("maybe\n");
if(a[l]!=x && a[r]!=y) printf("maybe\n");
else if(a[l]!=x || a[r]!=y){
//注意如果两个端点只知道一个也是能判必错的
int tmp=(l+<=r-(a[r]==y) ? qrv(,,n,l+,r-(a[r]==y)) : );
if(a[l]!=x ? b[r]<=tmp : b[l]<=tmp) printf("false\n");
else printf("maybe\n");
}
else if(b[r]>b[l]) printf("false\n");
else{
int tmp=(l+<=r- ? qrv(,,n,l+,r-) : );
if(b[r]<=tmp) printf("false\n");
else if(qru(,,n,l,r)) printf("maybe\n");
else printf("true\n");
}
}
return ;
}