NOIP 2013 火柴排队

很经典的一道题了，然而以前一直懒得做Orz 离散化+树状数组求逆序对

BZOJ 1067 [SCOI2007]降雨量

todolist清理计划--; 很久很久以前暑假留的作业= = 将年份离散化，用线段树简单的维护最值，然后依照提议判断就好。

    #include <iostream>
    #include <cstdio>
    #define MAYBE cout << "maybe" << endl
    #define TRUE cout << "true" << endl
    #define FALSE cout << "false" << endl
    using namespace std;
    
    //define
    const int maxn = 50000 + 5;
    int year[maxn], val[maxn], tree[maxn << 2];
    int n, m;
    
    void build(int rt, int l, int r){
        if(l == r){
            tree[rt] = val[l];return ;
        }
        int mid = l + r >> 1;
        build(rt << 1, l ,mid);
        build(rt << 1 | 1, mid + 1, r);
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }  
    
    int query(int rt, int l, int r, int ll, int rr){
        if(ll <= l && r <= rr){
            return tree[rt];
        }
        int mid = l + r >> 1;
        int ans = -1 * 0x7f7f7f7f;
        if(ll <= mid)ans = max(ans, query(rt << 1, l, mid, ll, rr));
        if(rr > mid)ans = max(ans, query(rt << 1 | 1, mid + 1, r, ll, rr));
        return ans;
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin >> n;
        for(register int i = 1; i <= n; ++i)cin >> year[i] >> val[i];
        build(1, 1, n);
        cin >> m;
        while(m--){
            int x,y,u,v;
            cin >> y >> x;
            if(y >= x) { FALSE; continue; }
            u=lower_bound(year+1, year+n+1, y) - year;
            v=lower_bound(year+1, year+n+1, x) - year;
            if(y == year[u] && x == year[v]){
                if(val[u] < val[v]) FALSE;
                else if(v == u+1){
                    if(x == y+1)TRUE;
                    else MAYBE;
                }
                else{
                    int w = query(1, 1, n, u+1, v-1);
                    if(w >= val[v])  FALSE; 
                    else{
                        if(x-y == v-u)TRUE;
                        else MAYBE;
                    }
                }
            }
            else if(y != year[u] && x == year[v]){
                if(u == v) MAYBE;
                else{
                    int w = query(1, 1, n, u, v-1);
                    if(w >= val[v]) FALSE;
                    else MAYBE;
                }
            }
            else if(y == year[u] && x != year[v]) {
                if(v == u+1) MAYBE;
                else{
                    int w = query(1, 1, n, u+1, v-1);
                    if(val[u] <= w) FALSE;
                    else MAYBE;
                }
            }
            else if(y != year[u] && x != year[v]) MAYBE;
        }
        return 0;
    }