BZOJ1067/SCOI2007/降雨量

Posted on By 二价氢

很坑爹的一道RMQ问题

讨论一下情况,定义年份为年的降雨量为

输出true的条件

1.

2.,已知且

输出maybe的条件

1.若未知,

2.未知

3.,均未知

4.,,,且中至少一个未知

其余情况,输出false

我用的线段树

AC-Code

#include <iostream>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=50005,MAXM=10005;
int Year[MAXN],Rain[131072];
int n,m;
int yi,ri,ya,yb,maxrain,pYA,pYB;
void MakeTree(int root)
{
    if (root<65536)
    {
        MakeTree(root*2);
        MakeTree(root*2+1);
        Rain[root]=max(Rain[root*2],Rain[root*2+1]);
    }
}
int Query(int l,int r)
{
    int ans=0;
    l=l+65536-1;
    r=r+65536+1;
    while (!((l^r)==1))
    {
        if (!(l&1))
            ans=max(ans,Rain[l+1]);
        if ((r&1))
            ans=max(ans,Rain[r-1]);
        l>>=1;
        r>>=1;
    }
    return ans;
}
int Find(int x)
{
    return lower_bound(&Year[1],&Year[n+1],x)-Year;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&Year[i],&Rain[65536+i]);
    MakeTree(1);
    scanf("%d",&m);
    while (m--)
    {
        scanf("%d%d",&ya,&yb);
        pYA=Find(ya);pYB=Find(yb);
        int ans;
        bool cl=(pYA<=n&&ya==Year[pYA]),cr=(pYB<=n&&yb==Year[pYB]);
        if (!cr) pYB--;
        if (cl)
        {
            if (cr)
            {
                maxrain=Query(pYA+1,pYB-1);
                if (Rain[65536+pYA]<Rain[65536+pYB])
                    ans=0;
                else
                {
                    if (maxrain<Rain[65536+pYB])
                    {
                        if (yb-ya==pYB-pYA)
                            ans=1;
                        else
                            ans=-1;
                    }else
                        ans=0;
                }
            }else
            {
                maxrain=Query(pYA+1,pYB);
                if (maxrain<Rain[65536+pYA])
                    ans=-1;
                else
                    ans=0;
            }
        }else
        {
            if (cr)
            {
                maxrain=Query(pYA,pYB-1);
                if (maxrain<Rain[65536+pYB])
                    ans=-1;
                else
                    ans=0;
            }else
            {
                ans=-1;
            }
        }
        switch (ans){
            case 1:
                printf("true\n");
                break;
            case 0:
                printf("false\n");
                break;
            case -1:
                printf("maybe\n");
                break;
        }
    }
    return 0;
}