[洛谷 2471,loj 2279][SCOI2007]降雨量

题目链接

https://www.luogu.com.cn/problem/P2471

https://loj.ac/problem/2279

题解

大力分类讨论一下。

第一种情况，起始年和终止年的数据都未知，显然答案是 maybe。

第二种情况，起始年数据已知，终止年数据未知：

• 如果起始年降雨量小于等于区间内除起始年以外其他年份降雨量的最大值，答案是 false。
• 否则是 maybe。

第三种情况，起始年数据未知，终止年数据已知：

• 如果终止年降雨量小于等于区间内除终止年以外其他年份降雨量的最大值，答案是 false。
• 否则是 maybe。

最后一种情况，起始年和终止年数据皆已知：

• 如果区间内没有数据缺失，按题意要求比较即可。
• 否则需要看已有数据是否满足要求，如果不满足要求则是 false，否则是 maybe。

查询区间最大值可以用 ST 表来实现。

#include <cmath>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
struct node
{
 int y,r;
 bool operator<(const node&a)const
 {
  return y<a.y||(y==a.y&&r<a.r);
 }
}a[50005];
unordered_set<int> s;
int n,f[50005][25];
void init()
{
 for(int i=1;i<=n;i++)
  f[i][0]=a[i].r;
 for(int k=1;k<=16;k++)
  for(int i=1;i+(1<<k)-1<=n;i++)
   f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
}
int find(int l,int r)
{
 if(l>r)return 0;
 int k=log2(r-l+1);
 return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i].y>>a[i].r;
  s.insert(a[i].y);
 }
 init();
 int q;
 cin>>q;
 while(q--)
 {
  int x,y;
  cin>>y>>x;
  if(!s.count(y)&&!s.count(x))
   cout<<"maybe"<<endl;
  else if(!s.count(y)&&s.count(x))
  {
   int l=lower_bound(a+1,a+n+1,(node){y,0})-a,r=lower_bound(a+1,a+n+1,(node){x,0})-a;
   if(find(l,r-1)>=a[r].r)cout<<"false"<<endl;
   else cout<<"maybe"<<endl;
  }
  else if(s.count(y)&&!s.count(x))
  {
   int l=lower_bound(a+1,a+n+1,(node){y,0})-a,r=lower_bound(a+1,a+n+1,(node){x,0})-a;
   if(find(l+1,r-1)>=a[l].r)cout<<"false"<<endl;
   else cout<<"maybe"<<endl;
  }
  else
  {
   int l=lower_bound(a+1,a+n+1,(node){y,0})-a,r=lower_bound(a+1,a+n+1,(node){x,0})-a;
   if(a[r].r>a[l].r)cout<<"false"<<endl;
   else if(r-l+1==x-y+1)//all information got
   {
    if(find(l+1,r-1)>=a[r].r)cout<<"false"<<endl;
    else cout<<"true"<<endl;
   }
   else
   {
    if(find(l+1,r-1)>=a[r].r)cout<<"false"<<endl;
    else cout<<"maybe"<<endl;
   }
  }
 }
 return 0;
}