很坑爹的一道RMQ问题
讨论一下情况，定义年份为\(y_1,y_2\)，\(i\)年的降雨量为\(R_i\)
输出true的条件
1.\(R_{y_1}>R_{y_2}\)
2.\(\forall y_1<k<y_2\),\(R_{k}\)已知且\(R_k<R_{y_2}\)
输出maybe的条件
1.若\(R_{y_1}\)未知，\(\forall y_1<k<y_2,R_k<R_{y_2}\)
2.\(R_{y_2}\)未知
3.\(R_{y_1}\),\(R_{y_2}\)均未知
4.\(R_{y_1}>R_{y_2}\),\(\forall y_1<k<y_2\),\(R_{k},R_k<R_{y_2}\),且\(R_k\)中至少一个未知
其余情况，输出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;
}