LCIS

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9713 Accepted Submission(s): 4215

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<=10⁵).
The next line has n integers(0<=val<=10⁵).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10⁵)
OR
Q A B(0<=A<=B< n).

Output

For each Q, output the answer.

Sample Input

10 10

7 7 3 3 5 9 9 8 1 8

Q 6 6

U 3 4

Q 0 1

Q 0 5

Q 4 7

Q 3 5

Q 0 2

Q 4 6

U 6 10

Q 0 9

Sample Output

题意：求区间连续递增的最大个数，Q是询问区间内最大的LCIS

U是更新节点

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + ;

int llen[maxn << ], rlen[maxn << ], len[maxn << ], tree[maxn];

void pushup(int l, int r, int id)

{

    int m = (l + r) >> ;

    llen[id] = llen[id << ];

    rlen[id] = rlen[id <<  | ];

    if (tree[m + ] > tree[m])

    {

        if (llen[id << ] == m - l + )

            llen[id] += llen[id <<  | ];

        if (rlen[id <<  | ] == r - m)

            rlen[id] += rlen[id << ];

        len[id] = max(max(len[id << ], len[id <<  | ]), rlen[id << ] + llen[id <<  | ]);

    }

    else

        len[id] = max(len[id << ], len[id <<  | ]);

}

void build(int l, int r, int id)

{

    if (l == r)

    {

        scanf("%d", &tree[l]);

        len[id] = llen[id] = rlen[id] = ;

        return;

    }

    int m = (l + r) >> ;

    build(l,m,id<<);

    build(m+,r,id<<|);

    pushup(l, r, id);

}

int query(int ll, int rr, int l, int r, int id)

{

    if (ll <= l && r <= rr)

        return len[id];

    int m = (l + r) >> ;

    if (ll <= m && m < rr)

    {

        int l1 = query(ll, rr, l,m,id<<);

        int l2 = query(ll, rr, m+,r,id<<|);

        if (tree[m] < tree[m + ])

        {

            int le = max(ll, m - rlen[id << ] + );

            int ri = min(rr, m + llen[id <<  | ]);

            return max(max(l1, l2), ri - le + );

        }

        return max(l1, l2);

    }

    else if (rr <= m)

        return query(ll, rr, l,m,id<<);

    else

        return query(ll, rr, m+,r,id<<|);

}

void update(int a, int b, int l, int r, int id)

{

    if (a == l && a == r)//找到要更新的位置

    {

        tree[a] = b;

        return;

    }

    int m = (l + r) >> ;

    if (m >= a)

        update(a, b, l,m,id<<);

    else

        update(a, b, m+,r,id<<|);

    pushup(l, r, id);

}

int main()

{

    int t;

    scanf("%d\n", &t);

    while (t--)

    {

        int n, m;

        scanf("%d%d", &n, &m);

        build(, n - , );

        while (m--)

        {

            char c[];

            int a, b;

            scanf("%s %d %d", c, &a, &b);

            if (c[] == 'Q')

                printf("%d\n", query(a, b, , n - , ));

            else

                update(a, b, , n - , );

        }

    }

    return ;

}

巴特西

hdu 3308 线段树，单点更新求最长连续上升序列长度

LCIS

最新文章

热门文章

巴特西

hdu 3308 线段树，单点更新 求最长连续上升序列长度

LCIS

最新文章

热门文章

hdu 3308 线段树，单点更新求最长连续上升序列长度