• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

[SCOI2007]降雨量 线段树和区间最值(RMQ)问题

开发技术 开发技术 2周前 (07-31) 16次浏览

  这道题是比较经典的 (RMQ) 问题,找到X和Y年间的最值来进行判断真假 , 用线段树维护是比较简单好写的。然而这只是一个小判断,比较难的是判断
(maybe) 。如果没有想好直接打代码会调很久(没错就是我)。怎么维护查询区间最大值我就不再这里赘述了,不懂线段树的先去入门(此题也是线段树入门题)。我讲几个很坑的点(比较坑我的点):

  1.询问的X年降雨量不超过Y,但是中间年份降雨量一定小于X(注意X和Y顺序)。

  2.X可能等于Y+1年,也就是不用考虑中间年份。

  3.区间查询最值的操作要留意范围,不同情况下查询的范围是不一样的,这点需要自己理解。

  4.错的最多的 (maybe)(false) 的判断,要清楚知道哪个是已知量,哪个是未知量(特别是X和Y是未知量的时候)。

  本题中我分了四种情况分析,还有众多 (if)(else) ,需要格外小心。我对输出进行简化,应该会更加直观一点。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define mid (l+r)/2
#define ls(x) x<<1
#define rs(x) x<<1|1
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
typedef __int128 lll;
const int maxn = 2e5+9;
int t[maxn],n,m;  //t 记录区间最大值
int year[maxn],rain[maxn];

void update(int now,int l,int r,int pos,int value){
    if(l == r) {t[now] = value;return;}
    if(pos <= mid) update(ls(now),l,mid,pos,value);
    else update(rs(now),mid+1,r,pos,value);
    t[now] = max(t[ls(now)],t[rs(now)]);  //维护区间最大值
}

int query(int now,int l,int r,int x,int y){  //询问x到y区间最大值
    if(x <= l&&r <= y) return t[now];
    int an = 0;
    if(x <= mid) an = query(ls(now),l,mid,x,y);
    if(y > mid) an = max(an,query(rs(now),mid+1,r,x,y));
    return an;
}
int main(){
    speedUp_cin_cout  //读写优化
    #define maybe cout<<"maybe"<<endl;continue;//让输出没这么难看
    #define false cout<<"false"<<endl;continue;
    #define true cout<<"true"<<endl;continue;
    cin>>n;
    int y,r;
    For(i,1,n)  {
        cin>>y>>r;
        year[i] = y;
        rain[i] = r;
        update(1,1,n,i,r);
    }
    cin>>m;
    int Y,X,p1,p2,f1,f2; //p1 p2是在数组的位置,f1 f2两个标记记录X Y是否已知降水量
    For(i,1,m){
        cin >> Y >> X;
        p1 = lower_bound(year+1,year+1+n, Y) - year; //year在输入时保证是有序的
        p2 = lower_bound(year+1,year+1+n, X) - year;
        f1 = (p1 == n + 1|| year[p1] != Y) ? 0 : 1;
        f2 = (p2 == n + 1 ||year[p2] != X) ? 0 : 1;
        //两年都不知道,可以不管中间如何,都是未知的
        if(!f1 && !f2) {maybe}
        //两年都知道
        if(f1 && f2) {
            if(rain[p1] < rain[p2]) {false}        //X年降水量多于Y年,错
            if(Y + 1 == X ) {true}                 //X = Y+1年,中间没有其他年份,而X年降水量一定不大于Y,对
            if(p1 + 1 == p2) {maybe}               //X不是Y后一年,但是X和Y年间都不知道降雨量,未知
            int maxGap = query(1,1,n,p1+1,p2-1);   //X和Y间存在已知降水量的年份,在其中找到降雨量最大值
            if(maxGap >= rain[p2]) {false}         //大于等于都满足严格小于,错
            if(p2 - p1 == X - Y) {true}            //满足严格小于后再判断X和Y间每年降雨量是否都已知
            else maybe                             //不是都已知,即未知
        }
        //后一年不知道,p2 一定大于 p1,只可能是maybe或者false
        else if(f1){
            if( p1 + 1 == p2 ) {maybe}
            int maxGap = query(1,1,n,p1+1,p2-1);   //注意查询范围
            if(maxGap >= rain[p1]) { false }
            else maybe
        }
        //前一年不知道,p1 有可能等于 p2,只可能是maybe或者false
        else{
            if(p1  == p2 ) {maybe}
            int maxGap = query(1,1,n,p1,p2-1);    //注意查询范围
            if(maxGap >= rain[p2]) { false }
            else { maybe }
        }
    }
    return 0;
}

希望大家都能一次AC这道题<( ̄︶ ̄)↗[GO!]


喜欢 (0)