P2471 [SCOI2007] 降雨量

· · 题解

P2471 [SCOI2007] 降雨量

题目翻译：

题目的意思是给你某些年的降雨量，在有n次查询，给定两个年份x,y，问x年的降雨量是否是自y年以来最大的；

思路：

本题的时间过大，所以可以离散化。然后对于题目要求，是要求最大的，因此可以用线段树来维护区间最大值（因为是连续的，所以可以用其他算法）。而我们只需要找到在怎样的关系下为false,true,maybe

为false的情况：

1.当右端点年份确定，且中间年份最大降雨量大于等于右端点降雨量（中间有比它大的，所以他不是最大的）

2.当左端点年份确定，且中间年份最大降雨量大于等于左端点降雨量（题目要求，一定小于左端点的降雨量）

3.当左右端点年份都确定，且左端点降雨量小于等于右端点降雨量（题目要求的左端点的降雨量严格小于右端点，否则就应该是更前面的年份

为true的情况：

保证不为false情况后
1.当左右端点之差不等于左右端点年份之差（等价于年份不连续，也就是我前面所说的更好的判断区间连续的方法）

2.左端点不确定
3.右端点不确定

为maybe的情况：

不满足以上所有即可

细节：

因为是用线段数组维护区间最大值，所以我们要保证查询时的点是之前存在的，因此我们只需要找到左右第一个存在的年份。再用线段树查询。因此最后要特判l和r是否为一个年份和l是否小于r

完整代码：

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=5e4+5;
int tr[N*4],a[N];
map<int,int>t;
void build(int p,int l,int r){
    if(l==r){
        tr[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[p]=max(tr[lc],tr[rc]);
}

int query(int p,int l,int r,int ll,int rr){
    if(ll<=l && r<=rr)return tr[p];
    int mid=(l+r)>>1;
    int res=-2e9;
    if(ll<=mid)res=max(res,query(lc,l,mid,ll,rr));
    if(mid<rr)res=max(res,query(rc,mid+1,r,ll,rr));
    return res;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int y,r;
        cin>>y>>r;
        a[i]=r;
        t[y]=i;
    }
    build(1,1,n);
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x>=y){
            cout<<"false"<<endl;
            continue;
        }
        int l=x,r=y;
        if(t[y]==0 && t[x]==0){
            cout<<"maybe"<<endl;
            continue;
        }
        while(t[l]==0)l++;
        while(t[r]==0)r--;
        if(l==r){
            cout<<"maybe"<<endl;
            continue; 
        }
        int num=query(1,1,n,t[l]+int(t[x]!=0),t[r]-int(t[y]!=0));
        if((t[y]!=0 && num>=a[t[y]]) || (t[x]!=0 && num>=a[t[x]]) || (t[x]!=0 && t[y]!=0 && a[t[x]]<=a[t[y]]))cout<<"false"<<endl;
        else if(y-x!=t[y]-t[x] || t[x]==0 || t[y]==0)cout<<"maybe"<<endl;
        else cout<<"true"<<endl;
    }
}

线段树讲解