LCIS

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

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

1
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

1
1
4
2
3
1
2
5

Author

shǎ崽

思路：

n个数字，q个操作，有两种操作：1.Q询问操作：在x,y区间内最长的连续递增子序列的长度。2，替换操作，把下标为x数替换为y.

这种询问，单点更新操作一般都是用线段树做。之前一直想成了最长递增子序列。。。完全没有思路，，其实他只要求最长的连续子串长度。。注意：是最长的连续的子串。

这样就是很裸的线段树区间合并了，

实现代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

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

#define mid int m = (l + r) >> 1

const int M = 2e5+;

int lsum[M<<],sum[M<<],rsum[M<<],num[M];

void pushup(int l,int r,int rt){

    int k = r - l + ;

    mid;

    lsum[rt] = lsum[rt<<]; rsum[rt] = rsum[rt<<|];

    sum[rt] = max(sum[rt<<],sum[rt<<|]);

    if(num[m] < num[m+]){

        if(lsum[rt] == (k - (k >> ))) lsum[rt] += lsum[rt<<|];

        if(rsum[rt] == (k>>)) rsum[rt] += rsum[rt<<];

        sum[rt] = max(sum[rt],lsum[rt<<|]+rsum[rt<<]);

    }

}

void build(int l,int r,int rt){

     if(l == r){

        sum[rt] = lsum[rt] = rsum[rt]  = ;

        return ;

     }

     mid;

     build(lson);

     build(rson);

     pushup(l,r,rt);

}

void update(int p,int c,int l,int r,int rt){

    if(l == r){

        num[l] = c;

        return ;

    }

    mid;

    if(p <= m) update(p,c,lson);

    if(p > m) update(p,c,rson);

    pushup(l,r,rt);

}

int query(int L,int R,int l,int r,int rt){

    if(L <= l&&R >= r) return sum[rt];

    int ret = ;

    mid;

    if(L <= m) ret = max(ret,query(L,R,lson));

    if(R > m) ret = max(ret,query(L,R,rson));

    if(num[m] < num[m+]){

        ret = max(ret,min(m - L + ,rsum[rt<<])+min(R-m,lsum[rt<<|]));

    }

    return ret;

}

int main(){

    int t,n,q,x,y;

    char c;

    scanf("%d",&t);

    while(t--){

        cin>>n>>q;

        for(int i = ; i <= n;i ++){

            cin>>num[i];

        }

        build(,n,);

        for(int i = ;i < q;i ++){

            cin>>c>>x>>y;

            if(c == 'Q'){

                x++;y++;

                cout<<query(x,y,,n,)<<endl;

            }

            else{

                x++;

                update(x,y,,n,);

            }

        }

    }

    return ;

}

巴特西

hdu-3308 LCIS (线段树区间合并）

LCIS

最新文章

热门文章