BZOJ1067：[SCOI2007]降雨量

浅谈\(RMQ\)：https://www.cnblogs.com/AKMer/p/10128219.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1067

关于\(RMQ\)的部分应该是很裸的了，这题难在分类讨论上。

顺带推销一波我的杀蚂蚁和猪国杀。

模拟题不难的。

时间复杂度：\(O(nlogn+m)\)

空间复杂度：\(O(nlogn)\)

代码如下：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=5e4+11;

int n,m;

int f[17][maxn];

int year[maxn],rain[maxn],Log[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

void make_st() {

    Log[0]=-1;

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

        Log[i]=Log[i>>1]+1;

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

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

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

}

int query(int l,int r) {

	if(r<l)return 0;

    int x=Log[r-l+1];

    return max(f[x][l],f[x][r-(1<<x)+1]);

}

int main() {

    n=read();

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

        year[i]=read(),f[0][i]=rain[i]=read();

    make_st();m=read();

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

        int y=read(),x=read();

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

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

        int mx=query(posy+(year[posy]==y),posx-1);

		if(year[posy]!=y&&year[posx]!=x) {puts("maybe");continue;}

		if(year[posy]==y&&year[posx]!=x) {

			if(mx>=rain[posy]) {puts("false");continue;}

			else {puts("maybe");continue;}

		}

		if(year[posy]!=y&&year[posx]==x) {

			if(mx>=rain[posx]) {puts("false");continue;}

			else {puts("maybe");continue;}

		}

		if(year[posy]==y&&year[posx]==x) {

			if(rain[posy]<rain[posx]||mx>=rain[posx]) {puts("false");continue;}

			else if(x-y!=posx-posy) {puts("maybe");continue;}

			else {puts("true");continue;}

		}

    }

	return 0;

}

巴特西

BZOJ1067：[SCOI2007]降雨量

最新文章

热门文章