60分 P2471 降雨量 线段树
查看原帖
60分 P2471 降雨量 线段树
109220
Farkas_W楼主2020/8/5 15:40

加了一些注解

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const int N=5e4+10;
int n,m;
inline int read() //快读 
{
	int x=0,f=1;
	char c;c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+(c-'0');
		c=getchar();
	}
	return x*f;
}
struct node{
	int yi,li,ri;//yi 降雨量  li--区间左端点年份  ri--区间右端点年份 
}a[N*4];
void build(int k,int l,int r)//建树 
{
	if(l==r)
	{
		a[k].li=read();
		a[k].yi=read();
		a[k].ri=a[k].li;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	a[k].yi=max(a[k<<1].yi,a[k<<1|1].yi);//存区间最大值 
	a[k].li=a[k<<1].li;
	a[k].ri=a[k<<1|1].ri;
}
int ask(int k,int l,int r,int x) //单点询问,若未知则输出0 
{
	if(x<a[k].li||x>a[k].ri)return 0;
	if(x==a[k].li&&a[k].li==a[k].ri)return a[k].yi;
	int mid=l+r>>1;
	return max(ask(k<<1,l,mid,x),ask(k<<1|1,mid+1,r,x));
}
int query(int k,int l,int r,int x,int y)//询问【x,y】区间最大值 
{
	if(y<a[k].li||x>a[k].ri)return 0;
	if(x<=a[k].li&&a[k].ri<=y)return a[k].yi;
	int mid=l+r>>1;
	return max(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
}
bool lll(int k,int l,int r,int x,int y)//判断【x,y】区间是否有年份未知 
{
	if(y<a[k].li||x>a[k].ri)return 0;
	if(x<=a[k].li&&a[k].ri<=y)
	{
		if(a[k].ri-a[k].li!=r-l)return 1;
		return 0;
	}
	int mid=l+r>>1;
	return max(lll(k<<1,l,mid,x,y),lll(k<<1|1,mid+1,r,x,y));
}
int main()
{
	int i,j;
	n=read();
	build(1,1,n);
	m=read();
//	for(i=1;i<=11;i++)
//	cout<<a[i].li<<" "<<a[i].ri<<" "<<a[i].yi<<endl;
	while(m--)
	{
		int x,y;
		y=read();x=read();
		if(y>=x)
		{
			printf("false\n");
			continue;
		}
		int x1=ask(1,1,n,x),yy=ask(1,1,n,y),q=query(1,1,n,y+1,x-1);
//		cout<<x1<<" "<<yy<<" "<<q<<" ";
		if(x1>0&&q>=x1)//左端点年份确定,且中间年份最大降雨量大于等于右端点降雨量
		{
			printf("false\n");
			continue;
		}
		if(yy>0&&q>=yy)//当左端点年份确定,且中间年份最大降雨量大于等于左端点降雨量
		{
			printf("false\n");
			continue;
		}
		if(x1>0&&yy>0&&yy<=x1)//左右端点年份都确定,左端点降雨量小于等于右端点降雨量
		{
			printf("false\n");
			continue;
		}
		if(x1==0||yy==0)//左端点或右端点年份不确定
		{
			printf("maybe\n");
			continue;
		}
		if(lll(1,1,n,y,x)>0)//区间内有年份未知 
		{
			printf("maybe\n");
			continue;
		}
		printf("true\n");
	}
	return 0;
}
2020/8/5 15:40
加载中...