题解 P2471 【[SCOI2007]降雨量】

· · 题解

这题很恶心，需要注意的细节很多。

难怪省选/NOI-难度。

RMQ用ST表维护。

思路其实和楼下差不多，提供AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define dop(i,m,n) for(int i=m;i>=n;i--)
#define lowbit(x) (x&(-x))
#define ll long long
#define INF 2147483647
#define re register
#define Open(s) freopen(s".in","y",stdin);freopen(s".out","f",stdout);
#define Close fclose(stdin);fclose(stdout);
using namespace std;
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*f;
}
const int maxn=100010;
int Log[maxn],f[maxn][22],ad[maxn],q,ans,n,m,a,b,tmp,num,MAX;
inline int Max(int a,int b){return a>b?a:b;}
inline int Min(int a,int b){return a<b?a:b;}
inline int Getad(int x){return lower_bound(ad+1,ad+n+1,x)-ad;}
inline int QueryMax(int x,int y){
    if(x>y) return -INF;
    int k=Log[y-x+1];
    return Max(f[x][k],f[y-(1<<k)+1][k]);
}
int main(){
    n=read();
    Log[0]=-1;
    rep(i,1,n) ad[i]=read(),f[i][0]=read();
    rep(i,1,n) Log[i]=Log[i/2]+1;
    rep(i,1,20)
       for(int j=1;j+(1<<i)-1<=n;j++)
          f[j][i]=Max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
    m=read();
    while(m--){
      a=read();b=read();
      int x=Getad(a),y=Getad(b);
      bool nl=(x<=n && ad[x]==a), nr=(y<=n && ad[y]==b);
      if(nl){
        if(nr){
          q=QueryMax(x+1,y-1);
          if(f[x][0]<f[y][0]) ans=0;
          else if(q<f[y][0]){
            if(y-x==b-a) ans=1;
            else ans=-1;
          }
          else ans=0;
        }
        else{
          q=QueryMax(x+1,y-1);
          if(q<f[x][0]) ans=-1;
          else ans=0;
        }
      }
      else{
        if(nr){
          q=QueryMax(x,y-1);
          if(q<f[y][0]) ans=-1;
          else ans=0;
        }
        else ans=-1;
      }
      if(ans==1) puts("true");
      else if(ans==-1) puts("maybe");
      else puts("false");
    }
    return 0;
}