|
|
题目链接：http://poj.org/problem?id=2637
  /**//*
 题意：
给定N(N <= 50000)条信息，表示第yi年的降水量是ri，然后给出M(M <= 10000)
条询问，每条询问的格式是Y X，表示自从第Y年以来X这一年是最大的降水量，问这句
话正确与否。
正确的判断条件是：
1.Y到X这些年的所有年份的降水量已知。
2.Y的降水量 >= X的降水量。
3.对于每个Z，Y < Z < X，Z的降水量小于X的降水量。
可能正确的判断条件是：
其中有一年的降水量不知道。
错误的判断条件是：
其他情况。
题解：
二分 + 线段树（区间最值）
思路：
逻辑强题。首先记录下每个信息所在的连续块，如果两个信息的连续块相同，说明
它们之间的年份全部连续。年份的查找可以采用二分查找，然后就是分情况讨论了，对、
输入的两个年份Y和X，利用二分查找找到最大的小于等于给定年份的那条记录fY和fX。
一.如果两者查到的记录都在输入数据中出现过，然后判断他们是不是属于一个连续的块，
只需要下标索引即可，然后是两种情况：
1. 如果属于同一个连续块，说明中间的年份全部出现过，然后利用线段树查找fY的
年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果满足以下
条件：(Yr >= Xr && Zr < Xr)则说明条件属实，是true的情况，否则则是false。
2.如果不属于同一个连续块，说明中间的年份不是全部出现过，然后利用线段树查找
fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果满足
以下条件：(Yr >= Xr && Zr < Xr)则说明当前条件属实，但是也有可能没出现过的记录
破坏这个条件，所以是maybe的情况，否则则是false。
二.如果X能够查到，则利用线段树查找[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr
，如果满足以下条件：Zr < Xr则说明条件有可能属实，是maybe的情况，否则则是false。
三.如果Y能查到，这个条件就比较隐秘了，因为需要满足(Yr >= Xr && Zr < Xr)，而Zr
和Xr无从得知，但是我们可以知道Yr >= Xr > Zr，于是只要判断当前的Zr是否小于Yr。
如果成立，则是maybe，否则就是false。
四.最后一种情况就是X和Y的年份在先前的数据中都没有出现过，这肯定是maybe的情况。
 */
 #include <iostream>
using namespace std;
#define maxn 50010
int n, m;
struct point  {
int year, r;
}pt[maxn];
struct Tree {
int Max;
int l, r;
}T[maxn*4];
int MMax(int a, int b) {
return a > b ? a : b;
}
void Build(int p, int l, int r) {
T[p].l = l;
T[p].r = r;
  if(l == r) {
T[p].Max = pt[l].r;
return ;
 }
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].Max = MMax(T[p<<1].Max, T[p<<1|1].Max);
}
int Query(int p, int l, int r) {
if(r < T[p].l || l > T[p].r)
return 0;
if(l <= T[p].l && T[p].r <= r)
return T[p].Max;
return MMax(Query(p<<1, l, r), Query(p<<1|1, l, r));
}
int Binary(int val, int l, int r) {
int ans = 0;
while(l <= r) {
int m = (l + r) >> 1;
if(pt[m].year <= val) {
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
// 连续的块种类
int Coces[maxn];
int main() {
int i;
int t = 0;
while(scanf("%d", &n) != EOF) {
if(t++ && n) {
puts("");
}
for(i = 1; i <= n; i++) {
scanf("%d %d", &pt[i].year, &pt[i].r);
if(i == 1) {
Coces[i] = 1;
}else {
if(pt[i].year - pt[i-1].year == 1)
Coces[i] = Coces[i-1];
else
Coces[i] = Coces[i-1] + 1;
}
}
if(n)
Build(1, 1, n);
scanf("%d", &m);
int bufM = m;
while(bufM--) {
int Y, X;
int ans; // 0 true 1 maybe 2 false
scanf("%d %d", &Y, &X);
int fY = Binary(Y, 1, n);
int fX = Binary(X, 1, n);
if(pt[fY].year == Y && pt[fX].year == X) {
// 都能找到数据中有的年份
int Yr = Query(1, fY, fY);
int Zr = Query(1, fY+1, fX-1);
// Y+1 == X 的情况在这里Zr返回的是0，所以肯定满足
int Xr = Query(1, fX, fX);
if(Coces[fY] == Coces[fX]) {
// 之间的年份全部连续
if(Yr >= Xr && Zr < Xr) {
ans = 0;
}else
ans = 2;
}else {
// 之间的年份不连续
if(Yr >= Xr && Zr < Xr) {
ans = 1;
}else
ans = 2;
}
}else if(pt[fX].year == X) {
// X这一年数据中有
if(Y + 1 == X) {
// 当前两年连续
ans = 1;
}else {
int Zr = Query(1, fY+1, fX-1);
int Xr = Query(1, fX, fX);
if(Zr < Xr)
ans = 1;
else
ans = 2;
}
}else if(pt[fY].year == Y) {
int Yr = Query(1, fY, fY);
int Zr = Query(1, fY+1, fX);
if(Yr > Zr) {
ans = 1;
}else
ans = 2;
}else {
// X 和 Y 都没有出现，肯定是maybe
ans = 1;
}
if(!ans)
puts("true");
else if(ans == 1)
puts("maybe");
else
puts("false");
}
if(!n && !m) {
break;
}
}
return 0;
}
/**//*
4
2002 4920
2003 5901
2004 2832
2005 3890
2
2002 2005
2003 2005
3
1985 5782
1995 3048
2005 4890
2
1985 2005
2005 2015
*/
|