bzoj 1067: [SCOI2007]降雨量

题目链接：

题解：

很简单的一道题，但代码里有许多细节需要注意，切容易出错，调了三个小时OTZ

做一个st表维护区间最大值就

在获得年份在序列中的pos时二分

也可以维护平衡树查询pos

或者用直接用线段维护最大值同时维护区间中有多少年份

其次分情况讨论就好了

#include<cmath>

#include<cstdio>

#include<algorithm>

inline int read() {

	int x=0,f=1;

	char c=getchar() ;

	while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

	while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();

	return x*f;

}

const int maxn = 50007;

int a[maxn],b[maxn];int f[maxn][21],n;

void make_st() {

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

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

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

}

int query(int l,int r) {

	if (l>r)

        return-0x7fffffff;

	int q=log(r-l+1)/log(2);

	return std::max(f[l][q],f[r-(1<<q)+1][q]);

}

int getpos(int f) {

	int l=1,r=n,ret=0;

	while(l<=r) {

		int mid=l+r>>1;

		if(a[mid]<=f)ret=mid,l=mid+1;

		else r=mid-1;

	}

		return ret;

}

int main() {

	n=read();

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

		a[i]=read(),b[i]=read();f[i][0]=b[i];

	}

	make_st();

	int m=read() ;

	for(int a1,b1;m--;) {

		a1=read() ,b1=read();

		int pa=getpos(a1),pb=getpos(b1);

		if(a[pa]!=a1&&a[pb]!=b1) {puts("maybe");continue;}

		if(a[pa]!=a1&&a[pb]==b1) {

			if(query(pa+1,pb-1)<b[pb])puts("maybe");

			else puts("false");continue;

		}

		if(a[pa]==a1&&a[pb]!=b1) {

			if(query(pa+1,pb)<b[pa])puts("maybe");

			else puts("false");continue;

		}

		if(pb-pa!=b1-a1) {

			if(query(pa+1,pb-1)>=b[pb]||b[pb]>=b[pa]) puts("false");

			else puts("maybe");continue;

		}

		if(query(pa+1,pb-1)<b[pb]&&b[pa]>b[pb]) puts("true");

		else puts("false");

		//printf("max(pa -> pb) : %d\n",query(pa+1,pb));

	}

	return 0;

}

巴特西

bzoj 1067: [SCOI2007]降雨量

题目链接：

题解：

最新文章

热门文章