题解 | #[SCOI2007]降雨量#

题面: 我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意 Y＜Z＜X，Z年的降雨量严格小于X年。 例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890， 则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。

首先我们要求区间的最值,我们第一个想到的肯定是 $STST$ 表, 肯定不会是线段树 然后因为有一些年份是未知的, 且数据范围很大, $\mathrm{-}10^9\le y_i\le 10^9-10^9\le y\_i\le 10^9$, 而 $nn$ 才 $10^{5}10^5$, 那我们肯定会想要离散化, 然后开始极其"简单"的分类了 我们 $XX$,$YY$, 在离散化后对应的下标为 $p1p1$, $p2p2$

一. 如果$X,YX,Y$ 都未知的时候, 显然是不能确定的

二. 如果$X,YX,Y$ 都已知的时候,
1.如果 $YY$ 的降雨量大于 $XX$ 的降雨量, 不满足 $XX$ 不超过 $YY$ 的条件
2.如果 $Y+1==XY\; +\; 1\; ==\; X$ 时, 则直接正确
3.如果 $p1+1==p2p1\; +\; 1\; ==\; p2$ 时, 则不能确定, 因为中间年份的降雨量未知
4.如果 $maxv\ge rain[p2]maxv\; \ge \; rain[p2]$ 则直接不正确, 因为 $maxvmaxv$ 必须要严格小于 $XX$ 的降雨量
5.如果 $p2-p1==x-yp2\; -\; p1\; ==\; x\; -\; y$ 说明 $XX$ ~ $YY$ 之间所有年份已知, 直接正确
6.否则不能确定

三.如果 $YY$ 已知, $XX$ 未知的时候
1.如果 $p1+1==p2p1\; +\; 1\; ==\; p2$, 则不能确定
2.如果 $maxv\ge rain[p1]maxv\; \ge \; rain[p1]$, 则不满足不超过 $YY$ 的降雨量 3.否则不能确定 四.如果 $XX$ 已知, $YY$ 未知的时候 1.如果 $p1==p2p1\; ==\; p2$, 则不能确定
2.如果 $maxvrain[p2]maxv\; rain[p2]$, 则不满足严格小于 $XX$ 的降雨量 3.否则不能确定

//  区间查询  ->ST表
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 10;

int f[N][20], rain[N], year[N], w[N], n, m;

void init()
{
	for(int j = 1; 1 << j <= n ; j ++ )
		for(int i = 1; i + (1 << j) - 1 <= n; i ++ )
		 f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r)
{
	int len = r - l + 1;
	int k = log(len) / log(2); 
	
	return max(f[l][k], f[r - (1 << k) + 1][k]);
}

signed main()
{
	cin >> n;

	for(int i = 1; i <= n; i ++ ) cin >> year[i] >> rain[i], f[i][0] = rain[i];

	init();
	cin >> m;
	while(m -- )
	{
		int x, y;
		cin >> y >> x;
      //离散化操作, p1, p2对应x,y离散化后的位置
		int p1 = lower_bound(year + 1, year + 1 + n, y) - year;
		int p2 = lower_bound(year + 1, year + 1 + n, x) - year;
		bool flag1 = (p1 == n + 1 || year[p1] != y) ? 0 : 1;
		bool flag2 = (p2 == n + 1 || year[p2] != x) ? 0 : 1;
      //flag1,flag2记录是否已知x,y
		if(!flag1 && !flag2)
		{
		 	cout << "maybe\n";
		 	continue;
		}
		if(flag1 && flag2)
		{
			if(rain[p1] < rain[p2])  //如果 Y 的降雨量大于 X 的降雨量, 不满足 X 不超过 Y 的条件
			{
				cout << "false\n";
				continue;
			}
			if(y + 1 == x)  //如果 Y + 1 == X 时, 则直接正确    
			{
			cout << "true\n";
			continue;
			}
			if(p1 + 1 == p2) //如果 p1 + 1 == p2 时, 则不能确定, 因为中间年份的降雨量未知   
			{
				cout << "maybe\n";
				continue;
			}
			int maxv = query(p1 + 1, p2 - 1);
			if(maxv >= rain[p2]) //如果 maxv ≥ rain[p2] 则直接不正确, 因为 maxv 必须要严格小于 X 的降雨量 
			{
				cout << "false\n";
				continue;
			}
			if(p2 - p1 == x - y)  //如果 p2 - p1 == x - y 说明 X ~ Y 之间所有年份已知, 直接正确  
			{
				cout << "true\n";
				continue;
			}
			else
			{
				cout << "maybe\n";
				continue;
			}
		}
		else if(flag1)
		{
			if(p1 + 1 == p2) 
			{
				cout << "maybe\n";
				continue;
			}
			int maxv = query(p1 + 1, p2 - 1); //如果 maxv ≥ rain[p1], 则不满足不超过 Y 的降雨量
			if(maxv >= rain[p1])
			{
				cout << "false\n";
				continue;
			}
			else
			{
				cout << "maybe\n";
				continue;
			}
		}
		else
		{
			if(p1 == p2)
			{
				cout << "maybe\n";
				continue;
			}
			int maxv = query(p1, p2 - 1);
			if(maxv >= rain[p2]) //maxv  rain[p2], 则不满足严格小于 X 的降雨量
			{
				cout << "false\n";
				continue;
			}
			else
			{
				cout << "maybe\n";
				continue;
			}
		}
	}		
}