洛谷 2471

---

题意：给定一些(n个)按升序排好的年份和对应的降雨量，年份不会重复，但是有可能会遗漏。又有q个描述(x,y), 描述的是“y年的降雨量是继x年以来最高的”，如果 降雨量x>=降雨量 y 且对于任意的 x<z<y, 都有 降雨量 z< 降雨量 y , 那么我们说这句话是 “对的”。如果找的到 x,y,z 不满足上述关系，那么这句话是 “错的”，否则这句话是 “可能对” 的 (因为遗漏年份的降水量无法确定)。$(n,k<=5*10^4)$

对于所有对的的描述，输出”true”, 错的输出”false”, 可能对的输出”maybe”。

思路，我们可以通过判断以下几个量来获得这句话的真伪

x,y 是否已知

x.val,y.val(即 x,y 年的降水量)

(x,y) 区间内是否有未知量

(x,y) 区间内的最大值 mx

true. 这句话是真的当且仅当:

lr已知，l.val>=r.val,mx<r.val,(x,y) 内无未知量

maybe. 这句话可能为真当且仅当下面一项成立:

lr 未知

l知r未知,r.val>mx

l 未知 r 知,mx<r.val

lr 已知,mx<r.val,l>=r.val

false. 余下的情况这句话不成立

因此，这道题只需要建立线段树保存区间最大值，区间是否有未知年份，区间的左右端是否有未知年份即可，只是讨论比较复杂.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>

#define MX 500000
#define ls (node*2)
#define rs (node*2+1)
#define mid ((l+r)/2)

using namespace std;

map<int,int> mp;
typedef struct tnd{
    int l,r;
    int eptl,eptr,epta,mx;
}treend;
typedef struct yr{
    int year,val;
}yrsl;
typedef struct qrs{
    int mx,ept;
}qtype;
int n,q;
treend tree[MX];
yrsl src[MX];

void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&src[i].year,&src[i].val),mp[src[i].year]=i;
    scanf("%d",&q);
}

void build(int node,int l,int r)
{
    tree[node].l=l,tree[node].r=r;
    if(l==r)
    {
        tree[node].mx=src[l].val;
        if(src[l].year!=src[l-1].year+1)tree[node].eptl=1;
        if(src[r].year!=src[r+1].year-1)tree[node].eptr=1;
    }
    else
    {
        build(ls,l,mid),build(rs,mid+1,r);
        tree[node].eptl=tree[ls].eptl,tree[node].eptr=tree[rs].eptr;
        tree[node].epta=tree[ls].eptr||tree[ls].epta||tree[rs].epta;
        tree[node].mx=max(tree[ls].mx,tree[rs].mx);
    }
}

qtype query(int node,int ql,int qr)
{
    int l=tree[node].l,r=tree[node].r;
    int yl=src[l].year,yr=src[r].year;
    qtype rt,r1,r2;
    rt.ept=0,rt.mx=-2000000000;
    if(ql<yl&&yr<qr)rt.ept=tree[node].epta||tree[node].eptl||tree[node].eptr,rt.mx=tree[node].mx;
    else if(yr==ql)rt.ept=tree[node].eptr;
    else if(yl==qr)rt.ept=tree[node].eptl;
    else if(ql>=yr||qr<=yl);
    else
    {
        r1=query(ls,ql,qr),r2=query(rs,ql,qr);
        rt.ept=r1.ept||r2.ept,rt.mx=max(r1.mx,r2.mx);
    }
    return rt;
}

void work()
{
    int a,b,lz,rz;
    qtype rt;
    for(int i=1;i<=q;i++){
        scanf("%d%d",&a,&b);
        if(a>b)cout<<"false\n";
        else
        {
            rt=query(1,a,b);
            lz=mp[a],rz=mp[b];
            if(lz&&rz&&src[lz].val>=src[rz].val&&rt.mx<src[rz].val&&rt.ept==0)cout<<"true\n";
            else if((lz==0&&rz==0)||
                    (lz>=1&&rz==0&&src[lz].val>rt.mx)||
                    (lz==0&&rz>=1&&rt.mx<src[rz].val)||
                    (lz>=1&&rz>=1&&rt.mx<src[rz].val&&src[lz].val>=src[rz].val&&rt.ept==1))cout<<"maybe\n";
            else cout<<"false\n";
        }
    }
}

int main()
{
    input(),build(1,1,n),work();
    return 0;
}