BZOJ 1067 降雨量

Description

我们常常会说这样的话：“(X)年是自(Y)年以来降雨量最多的”。它的含义是(X)年的降雨量不超过(Y)年，且对于任意(Y＜Z＜X)，(Z)年的降雨量严格小于(X)年。例如(2002，2003，2004)和(2005)年的降雨量分别为(4920，5901，2832)和(3890)，则可以说“(2005)年是自(2003)年以来最多的”，但不能说“(2005)年是自(2002)年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。

Input

输入仅一行包含一个正整数(n)，为已知的数据。以下(n)行每行两个整数(y_{i})和(r_{i})，为年份和降雨量，按照年份从小到大排列，即(y_{i}＜y_{i}+1)。下一行包含一个正整数(m)，为询问的次数。以下(m)行每行包含两个数Y和X，即询问“(X)年是自(Y)年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

对于每一个询问，输出true，false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

(100\%)的数据满足：(1 le n le 50000, 1 le m le 10000, -10^{9} le y_{i} le 10^{9}, 1 le r_{i} le 10^{9})

线段树或rmq都可以做啊。

#include<cstdio>
#include<cstdlib>
using namespace std;

#define inf (1<<30)
#define maxn (50010)
#define maxm (10010)
int n,m;
struct node
{
	int a,b;
	inline void read() { scanf("%d %d",&a,&b); }
	friend inline bool operator >(const node &x,const node &y) { return x.b != y.b?x.b>y.b:x.a<y.a; }
	friend inline bool operator != (const node &x,const node &y) { return x.a!=y.a||x.b!=y.b; }
}rain[maxn],seg[maxn*4];

inline node Max(const node &x,const node &y) { if (x > y) return x; return y; }

inline int find(int key)
{
	int l = 1,r = n;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (rain[mid].a <= key) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}

inline void build(int l,int r,int now)
{
	if (l == r) { seg[now] = rain[l]; return; }
	int mid = (l + r) >> 1;
	build(l,mid,now<<1); build(mid+1,r,now<<1|1);
	seg[now] = Max(seg[now<<1],seg[now<<1|1]);
}

inline node ask(int l,int r,int now,int ql,int qr)
{
	if (ql > qr) return (node){-inf,-inf};
	if (l >= ql&&r <= qr) return seg[now];
	int mid = (l + r) >> 1;
	if (qr <= mid) return ask(l,mid,now<<1,ql,qr);
	else if (ql > mid) return ask(mid+1,r,now<<1|1,ql,qr);
	else return Max(ask(l,mid,now<<1,ql,mid),ask(mid+1,r,now<<1|1,mid+1,qr));
}

int main()
{
	freopen("1067.in","r",stdin);
	freopen("1067.out","w",stdout);
	scanf("%d",&n);
	for (int i = 1;i <= n;++i) rain[i].read();
	rain[0].a = -inf;
	build(1,n,1);
	scanf("%d",&m);
	for (int i = 1;i <= m;++i)
	{
		int x,y; scanf("%d %d",&x,&y);
		int l = find(x)-1,r = find(y)-1;
		if (rain[l].a != x&&rain[r].a != y) printf("maybe
");
		else if (rain[l].a == x && rain[r].a == y)
		{
			if (ask(1,n,1,l,r-1) != rain[l]||ask(1,n,1,l+1,r) != rain[r]) printf("false
");
			else
			{
				if (rain[l].b < rain[r].b) printf("false
");
				else
				{
					if (r-l+1 == y-x+1) printf("true
");
					else printf("maybe
");
				}
			}
		}
		else
		{
			if (rain[l].a == x)
			{
				if (ask(1,n,1,l,r) != rain[l]||ask(1,n,1,l+1,r).b == rain[l].b) printf("false
");
				else printf("maybe
");
			}
			else
			{
				if (ask(1,n,1,l+1,r) != rain[r]) printf("false
");
				else printf("maybe
");
			}
		}
	}
	fclose(stdin); fclose(stdout);
	return 0;
}