|
|
題目鏈接：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
*/
|