原题传送门

前置芝士

正文

首先我们来分析一下题意。

题目会给出两个大小为 \(n\) 的数组，\(y\) 和 \(r\) ，其中 \(y_i\) 表示第 \(i\) 个年份是第几年，\(r_i\) 表示的是第 \(y_i\) 年的降雨量。之后，将会有 \(m\) 次询问，每次询问给出两个年份 \(Y\) 和 \(X\) ，若用 Z 表示 \(Y\) 和 \(X\) 之间的年份，则我们要判断的是三个年份的降雨量是否满足 \(Y\geqslant X>Z\) ，根据判断结果输出不同的话。

很显然，这是一个 \(RMQ\) 问题， \(RMQ\) 问题有多种方式解决，下面将只给出 \(ST\)表的解法。(其实我不会线段树，单调栈也忘记怎么写了)

这道题看似是一道水题，其实它有非常多的坑点，因为题目中的 \(Y,X,Z\) 之间会有很多种大小关系，而对于每一种关系，我们都要判断输出的结果是 \(true\) ，\(false\) ，还是 \(maybe\) ，这就使得这道题会让人变得非常头疼。

对于 \(Y,X,Z\) 三者之间大小关系的分析，将直接在代码中给出。

然而，我们并不是只需判断 \(Y,X,Z\) 之间的关系，在某些情况下，我们还需判断 \(Y,X\) 之间所有年份的降水量是否已知。为了防止超时爆零，我们不能直接用 \(for\) 循环枚举判断，但是我们可以利用二分法查找中间年份，这样就不会超时。

因为这题的数据范围特别大， \(y_i\) 在 \(\pm 10^9\) 之间，我们不可能定义一个大小有 \(2*10^9\) 的数组来存储每一年的降水量，所以我们需要对所给的年份进行离散化处理。但是，题目中所给出的年份本来就是从小到大排列的，这就帮我们省去了离散化的步骤（即给出的已经处于离散化状态），我们只要直接按照所给顺序做就行。

代码如下：

#include<bits/stdc++.h>

#include<vector>

using namespace std;

typedef long long ll;

const int N=50005;

int a[N],b[N],d[N][20],lg[N]= {-1};

int n,m;

int query(int x) {

	return lower_bound(a+1,a+1+n,x)-a;

}

void RMQ_init(int n) {

	for (int i=1; i<=n; i++) {

		d[i][0]=b[i];

		lg[i]=lg[i/2]+1;

	}

	for (int j=1; 1<<j<=n; j++) {

		for (int i=1; i+(1<<j)-1<=n; i++) {

			d[i][j]=max(d[i][j-1],d[i+(1<<j-1)][j-1]);

		}

	}

}

int RMQ(int l,int r) {

	if (l>r) return -1;

	int k=lg[r-l+1];

	return max(d[l][k],d[r-(1<<k)+1][k]);

}

int main() {

	scanf("%d",&n);

	for (int i=1; i<=n; i++) scanf("%lld %lld",&a[i],&b[i]);

	RMQ_init(n);

	scanf("%d",&m);

	for (int _=1; _<=m; _++) {

		ll o,p;

		scanf("%lld %lld",&o,&p);

		int x=query(p),y=query(o);

		int rmq=RMQ(y+1,x-1);

		if (y>x) {

			puts("false");

		} else {

			if (x<=n && a[x]==p) {

				//x年份存在

				if (y<=n && a[y]==o) {

					//y年份存在

					bool now=1;

					if (rmq==-1) {

						//x,y中间无已知年份时

						if (b[x]<=b[y]) { //x的降雨量小于等于y

							if (p-o==x-y) puts("true"); //x，y为连续的两年

							else puts("maybe");//x，y中间有其他年份

						} else {

							puts("false");//x的降雨量大于y

						}

						now=0;

					}

					if (!now) goto M;

					if (b[y]<b[x] || b[x]<=rmq) {

						//y年降雨量比x年小或者x~y之间有一年的降雨量大于x年

						puts("false");

					} else {

						//b[y]>b[x]>rmq

						if (x-y!=p-o) {

							//第i年的降雨量未知

							puts("maybe");

						} else puts("true"); //中间年份全部存在

					}

				} else {

					//y年不存在

					if (RMQ(y,x-1)>=b[x]) {

						//ps:此时，第一个降雨量大于等于p的年份，

						//	 也就是中间年份的第一项就是y。 

						//中间年份存在降雨量大于等于x年的一年

						puts("false");

					} else {

						//y年不存在，无论中间年份降雨量如何，结果都是未知的

						puts("maybe");

					}

				}

			} else {

				//x年不存在

				if (y<=n && a[y]==o) {

					//y年存在

					if (rmq>=b[y]) puts("false"); //rmq>=a[y]时

					else puts("maybe");//a[y]>rmq时，x年未知

				} else puts("maybe");//x，y都未知时。

			}

		}

		M:;

	}

	return 0;

}

祝各位大佬早日 \(AKIOI\) 。

巴特西

题解 P2471 【[SCOI2007]降雨量】

原题传送门

前置芝士

离散化

ST表和RMQ问题

二分

正文

最新文章

热门文章