bzoj 1067: [SCOI2007]降雨量-白红宇

bzoj 1067: [SCOI2007]降雨量

阅读量：7058 次

发布时间：2019-06-28

本文共 1779 字，大约阅读时间需要 5 分钟。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 50008 5 using namespace std; 6 struct shu 7 { 8     int l,r,ma; 9 }shu[4*M];10 int l,r,n,m,b[M],a1[M],a2[M];11 void jian(int b1,int l,int r)12 {13     shu[b1].l=l;14     shu[b1].r=r;15     if(l==r)16       {17         shu[b1].ma=a2[l];18         return;19       }20     int mid=(l+r)>>1;21     jian(b1*2,l,mid);22     jian(b1*2+1,mid+1,r);23     shu[b1].ma=max(shu[b1*2].ma,shu[b1*2+1].ma);24     return;25 }26 int zhao(int b1,int l,int r)27 {28     if(shu[b1].l>=l&&shu[b1].r<=r)29       return shu[b1].ma;30     int mid=(shu[b1].l+shu[b1].r)>>1,mx=-100000000;31     if(l<=mid)32       mx=max(zhao(b1*2,l,r),mx);33     if(r>mid)34       mx=max(zhao(b1*2+1,l,r),mx);35     return mx;36 }37 int main()38 {39     scanf("%d",&n);40     for(int i=1;i<=n;i++)41       scanf("%d%d",&a1[i],&a2[i]);42     jian(1,1,n);43     scanf("%d",&m);44     for(int i=1;i<=m;i++)45       {46         int b1,b2,b3,c1,c2;47         scanf("%d%d",&c1,&c2);48         b1=lower_bound(a1+1,a1+n+1,c1)-a1;49         b2=lower_bound(a1+1,a1+n+1,c2)-a1;50         if(a1[b1]==c1)51             b3=zhao(1,b1+1,b2-1);52         else53             b3=zhao(1,b1,b2-1);54         if(a1[b1]==c1&&a1[b2]==c2&&a2[b1]>a2[b2]&&a2[b2]>b3&&b2-1-b1==c2-c1-1)55           printf("true\n");56         else  if((a1[b1]==c1&&a1[b2]!=c2&&a2[b1]<=b3)||(a1[b2]==c2&&a1[b1]!=c1&&a2[b2]<=b3)57           ||(a1[b1]==c1&&a1[b2]==c2&&(a2[b1]
        
         <=b3)))58                  printf("false\n");59               else60                  printf("maybe\n");61       }62     return 0;63 }