【Luogu P2471】[SCOI2007]降雨量

Luogu P2471

啊啊啊啊这真是一道史上最毒瘤的题目！！！！！

题意就是给出n个年份的降雨量

询问：“自从\(y\)年以来\(x\)年的降雨量最大”的正确性。

显然有多种情况需要考虑，那么就需要通过分类讨论理清程序的逻辑了。

对于“自从\(y\)年以来\(x\)年的降雨量最大”这样一句话，可以转化成如下条件：

\(rain[x]<=rain[y]且\forall a \in [y+1,x-1]有rain[a]<rain[x]\)

经过这样的转化，我们就可以对各种情况进行分类讨论了。

定义：\(query(x,y)\)等于\(rain[x...y]\)的最大值

\[ ①rain[y]未知，rain[x]已知的情况：若此时query(y+1,x-1)>=rain[x]则导出false，反之则导出maybe\\
②rain[x]未知，rain[y]已知：若此时query(y+1,x-1)>=rain[y]则导出false,反之则导出maybe\\
③rain[x]、rain[y]均未知：则导出maybe\\
④两者皆已知：rain[x]>rain[y]导出false；query(y+1,x-1)>=rain[x]导出false\\
若以上两个条件均不符合，则不可能再导出false\\
此时再判断：若\exists a \in [y+1,x-1] 有rain[a]未知，则导出maybe\\
以上所有情况皆不符合则导出true
\]

那么剩下的事情就是把这个东西写成代码了。

Query函数可以用线段树或者st表实现。

如果使用线段树，请记住开4倍空间。

否则将像我一样疯狂WA50。（血的教训）

#include<cstdio>

#include<algorithm>

#define lson root<<1

#define rson root<<1|1

#define mid ((l+r)>>1)

using namespace std;

int tree[4*50005],rain[50005],year[50005],n,m,x,y;

void push_up(int root)

{

	tree[root]=max(tree[lson],tree[rson]);

}

void build(int root,int l,int r)

{

	if (l==r)

	{

		tree[root]=rain[l];

		return ;

	}

	build(lson,l,mid);

	build(rson,mid+1,r);

	push_up(root);

}

int query_max(int root,int l,int r,int al,int ar)

{

	if (al<=l&&r<=ar) return tree[root];

	if (l>ar||al>r) return 0;

	int ret=0;

	ret=max(ret,query_max(lson,l,mid,al,ar));

	ret=max(ret,query_max(rson,mid+1,r,al,ar));

	return ret;

}

int main()

{

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d%d",&year[i],&rain[i]);

	build(1,1,n);

	scanf("%d",&m);

	for (int i=1;i<=m;i++)

	{

		scanf("%d%d",&y,&x);

		if (x<=y)

		{

			printf("false\n");

			continue;

		}

		int locx=lower_bound(year+1,year+n+1,x)-year;

		int locy=lower_bound(year+1,year+n+1,y)-year;

		if (x==y+1)//其实不需要特判，只要在query函数中加一个判断，如果区间不合法则返回0即可。

		{

			if (year[locx]!=x) printf("maybe\n");

			else if (year[locy]!=y) printf("maybe\n");

			else if (rain[locx]<=rain[locy]) printf("true\n");

			else printf("false\n");

			continue;

		}

		else

		{

			int lx=year[locx],ly=year[locy];

			if (lx==x&&ly!=y)

			{

				if (query_max(1,1,n,locy,locx-1)>=rain[locx]) printf("false\n");

				else printf("maybe\n");

			}

			if (lx!=x&&ly==y)

			{

				if (query_max(1,1,n,locy+1,locx-1)>=rain[locy]) printf("false\n");

				else printf("maybe\n");

			}

			if (lx!=x&&ly!=y) printf("maybe\n");

			if (lx==x&&ly==y)

			{

				if (rain[locx]<=rain[locy])

				{

					if (query_max(1,1,n,locy+1,locx-1)<rain[locx])

					{

						if (locx-locy==x-y) printf("true\n");

						else printf("maybe\n");

					}

					else printf("false\n");

				}

				else printf("false\n");

			}

		}

	}

	return 0;

}

巴特西

【Luogu P2471】[SCOI2007]降雨量

最新文章

热门文章