bzoj1067: [SCOI2007]降雨量

不得不說是國文題，題目很短，條件略多。

貌似網上大部分人都是些RMQ的，我寫了個單調棧。不過速度上并沒有RMQ快（跑了300+ms），不知道是不是代碼寫渣了。

大概的思路就是維護每一年的 第一個大于等于當年的降水量的年份（往年 和 未來 的年份都要，是以要做兩遍），時間複雜度O（n）。

具體的分析可見huzecong的分析，寫的很詳細。

需要注意的是年份的範圍是-10^9<=yi<=10^9，棧的初始化要是-INF。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 50010;
const int INF = 1999999999;
int a[MAXN], b[MAXN], c[MAXN], year[MAXN], rain[MAXN], n;
struct stack
{
    int y, v;
}s[MAXN],cur;
 
bool find(int x, int &xx)
{
    int l = 1, r = n, mid;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (year[mid] == x)
        {
            xx = mid;
            return 1;
        }
        else if (year[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
    while (year[r] >= x) --r;
    xx = r;
    return 0;
}
 
void work()
{
    int i, j, m, top = 0, last = 0, x, y, xx, yy;
    bool b1, b2;
    scanf("%d", &n);
    b[0] = s[0].y = s[0].v = -INF;
     
    for (i = 1; i <= n; ++i)
    {
        scanf("%d%d", &cur.y, &cur.v);
        year[i] = cur.y; rain[i] = cur.v;
        while (top&&s[top].v < cur.v) --top;
        a[i] = s[top].y;
        s[++top] = cur;
        if (year[i - 1] + 1 != year[i]) b[i] = year[i] - 1;
        else b[i] = b[i - 1];
    }
    top = 0; s[0].y = INF;
    for (i = n; i; --i)
    {
        cur.y = year[i]; cur.v = rain[i];
        while (top&&s[top].v < cur.v) --top;
        c[i] = s[top].y;
        s[++top] = cur;
    }
    scanf("%d", &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &y, &x);
        b1 = find(x, xx);
        b2 = find(y, yy);
        if (b1&&b2)
        {
            if (a[xx] != y) printf("false\n");
            else if (b[xx] >= y) printf("maybe\n");
            else printf("true\n");
        }
        if (b1&&!b2)
        {
            if (a[xx] > y) printf("false\n");
            else printf("maybe\n");
        }
        if (!b1&&b2)
        {
            if (year[xx] == y || (c[yy] >= x&&rain[xx] < rain[yy])) printf("maybe\n");
            else printf("false\n");
        }
        if (!b1&&!b2) printf("maybe\n");
    }
}
 
int main()
{
    work();
    return 0;
}