HDU 6406 Taotao Picks Apples

题目链接

题意： n n n 棵苹果树，每棵苹果树有一个高度值。给了 m m m 组查询，每组查询给定 p p p 和 q q q，即当前查询假设第 p p p 棵苹果树的高度是 q q q，求从第一个位置开始的最长上升子序列（要求严格上升）。

思路：我们维护两个数组 d 1 [   ] d1[ \ ] d1[ ] 和 d 2 [   ] d2[ \ ] d2[ ]， d 1 [ i ] d1[i] d1[i]: 区间 [ 1 , i ] [1, i] [1,i] 最长上升子序列的长度； d 2 [ i ] d2[i] d2[i]: 区间 [ i , n ] [i, n] [i,n] 最长上升子序列的长度。那么对于每一组查询，对于 [ 1 , p − 1 ] [1, p-1] [1,p−1]的贡献是 d 1 [ p − 1 ] d1[p-1] d1[p−1]；我们找到区间 [ 1 , p − 1 ] [1, p-1] [1,p−1] 中的最大值 m x mx mx ，如果 q > m x q > mx q>mx，那么贡献 + 1 +1 +1；我们找区间 [ p + 1 , n ] [p + 1, n] [p+1,n] 中大于 m a x { m x , q } max\{mx, q\} max{mx,q} 的第一个数的 i d id id，那么该子区间的贡献是 d 2 [ i d ] d2[id] d2[id].

d 2 [ ] d2[] d2[] 数组的求法，遍历 i : n − 1 i: n-1 i:n−1，找到 [ i , n ] [i, n] [i,n] 中第一个大于 h [ i ] h[i] h[i] 的位置 i d id id，那么 d 2 [ i ] = d 2 [ i d ] + 1 d2[i] = d2[id] + 1 d2[i]=d2[id]+1

#include <bits/stdc++.h>

#define MID (l + r) >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid + 1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr

using namespace std;
typedef long long ll;

int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

const int maxN = 1e5 + 10;
int n, m, h[maxN];
int d1[maxN]; //d1[i]: 区间[1, i]最长上升子序列的长度
int d2[maxN]; //d2[i]: 区间[i, n]最长上升子序列的长度
//d2[]数组的求法，遍历i: n~1，找到[i, n]中第一个大于h[i]的位置id，d2[i] = d2[id] + 1
int tree[maxN << 2]; //维护区间最大值

void pushup(int rt) {
    tree[rt] = max(tree[lsn], tree[rsn]);
}

void build(int rt, int l, int r) {
    if (l == r) {
        tree[rt] = h[l];
        return;
    }
    int mid = MID;
    build(Lson);
    build(Rson);
    pushup(rt);
}

int query(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return tree[rt];
    int mid = MID;
    if (qr <= mid) return query(QL);
    else if (ql > mid) return query(QR);
    else return max(query(QL), query(QR));
}

int fid(int rt, int l, int r, int ql, int qr, int val) { //找[ql, qr]区间中第一个大于val的值的位置，如果没有返回-1
    if (l == r) {
        if (tree[rt] > val) return l;
        else return -1;
    }
    if (ql <= l && qr >= r) {
        if (tree[rt] <= val) return -1;
    }
    int mid = MID;
    if (qr <= mid) return fid(QL, val); //先找左区间
    else if (ql > mid) return fid(QR, val);
    int tmp = fid(QL, val); //先找左区间
    if (tmp != -1) return tmp;
    return fid(QR, val); //再找右区间
}

int main() {
    int TAT = read();
    while(TAT -- ) {
        n = read(); m = read();
        for(int i = 1; i <= n; ++ i ) {
            h[i] = read();
        }
        build(1, 1, n);
        int lst = 0;
        for(int i = 1; i <= n; ++ i ) {
            if(h[i] > h[lst]) {
                d1[i] = d1[lst] + 1;
                lst = i;
            } else {
                d1[i] = d1[i - 1];
            }
        }
        d2[n] = 1;
        for(int i = n - 1; i >= 1; -- i ) {
            int id = fid(1, 1, n, i + 1, n, h[i]);
            if(id == -1) d2[i] = 1;
            else d2[i] = d2[id] + 1;
        }
        while(m -- ) {
            int p = read(), q = read();
            int ans = d1[p - 1];
            int mx = 0;
            if(p - 1 >= 1) mx = query(1, 1, n, 1, p - 1);
            if(q > mx) ++ ans, mx = q;
            int id = -1;
            if(p + 1 <= n) id = fid(1, 1, n, p + 1, n, mx);
            if(id != -1) ans += d2[id];
            printf("%d\n", ans);
        }
//        fflush(stdout);
    }
    return 0;
}
/*
1
5 3
1 2 3 4 4
1 5
5 5
2 3
 */