HDU 3308 – LCIS [线段树区间合并]

LCIS

Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
Output
For each Q, output the answer.
题意:给你n个数,有两种操作,一种是更换某个数值(单点更新),另外一种是输出最长的连续递增序列的长度(区间查询);
分析:如果使用一般算法,单点更新很快,但是区间查询就不行了,所以需要使用线段树。最近做的线段树比较多,本题需要区间合并,即pushUp函数需要对合并子区间的最长递增序列到父区间,同时查询的时候要注意分情况讨论,也需要合并区间操作。
CPP代码:
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

const int maxn = 1e5+7;
int llen[maxn<<2], rlen[maxn<<2], mlen[maxn<<2];
int num[maxn];

void pushUp(int l, int r, int rt) {
    llen[rt] = llen[rt<<1];
    rlen[rt] = rlen[rt<<1|1];
    mlen[rt] = max(mlen[rt<<1], mlen[rt<<1|1]);
    int mid = (l + r) >> 1, len = r - l + 1;
    if(num[mid] < num[mid+1]) {
        if(llen[rt] == len-(len>>1)) llen[rt] += llen[rt<<1|1];
        if(rlen[rt] == (len>>1)) rlen[rt] += rlen[rt<<1];
        mlen[rt] = max(mlen[rt], rlen[rt<<1] + llen[rt<<1|1]);
    }
}

void build(int l, int r, int rt) {
    if(l == r) {
        scanf("%d", &num[l]);
        llen[rt] = rlen[rt] = mlen[rt] = 1;
        return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    pushUp(l, r, rt);
}

void update(int p, int x, int l, int r, int rt) {
    if(l == r) {
        num[l] = x;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) update(p, x, lson);
    else update(p, x, rson);
    pushUp(l, r, rt);
}

int query(int L, int R, int l, int r, int rt) {
    if(L <= l && R >= r)
        return mlen[rt];
    int m = (l + r) >> 1;
    if(R <= m) return query(L, R, lson);
    if(L > m) return query(L, R, rson);
    int ta = query(L, R, lson), tb = query(L, R, rson);
    int best = max(ta, tb);
    if(num[m] < num[m+1]) {
        ta = min(m-L+1, rlen[rt<<1]);
        tb = min(R-m, llen[rt<<1|1]);
        best = max(best, ta+tb);
    }
    return best;
}


int main() {
    int T; scanf("%d", &T);
    while(T--) {
        int n, m; scanf("%d%d", &n, &m);
        build(1, n, 1);
        for (int i = 0; i < m; ++i) {
            char op[3]; int x, y;
            scanf("%s%d%d", op, &x, &y);
            if(op[0] == 'Q') {
                ++x, ++y;
                printf("%d\n", query(x, y, 1, n, 1));
            } else {
                ++x;
                update(x, y, 1, n, 1);
            }
        }
    }
    return 0;
}

欢迎留言