LCIS

Time Limit: 6000/2000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5591 Accepted Submission(s): 2443

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ǎ崽

题解：开始看错题，以为是最长子序列，GG，

后知后觉，线段树秒了

///

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#include<bitset>

#include<set>

#include<vector>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define meminf(a) memset(a,127,sizeof(a))

#define memfy(a)  memset(a,-1,sizeof(a))

#define TS printf("111111\n");

#define FOR(i,a,b) for( int i=a;i<=b;i++)

#define FORJ(i,a,b) for(int i=a;i>=b;i--)

#define READ(a,b) scanf("%d%d",&a,&b)

#define mod 1000000007

#define inf 1000000001

#define maxn 200000+2

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//****************************************

struct ss

{

    int l,r,v,ans;

    int lc,rc;

}tr[maxn<<];

int a[maxn<<],n,q;

void push_up(int k)

{

    if(a[tr[k<<].r]<a[tr[k<<|].l])

    {

        tr[k].ans=max(max(tr[k<<].ans,tr[k<<|].ans),tr[k<<].rc+tr[k<<|].lc);

        if(tr[k<<].lc==(tr[k<<].r-tr[k<<].l+))

        {

            tr[k].lc=tr[k<<].lc+tr[k<<|].lc;

        }else  tr[k].lc=tr[k<<].lc;

        if(tr[k<<|].lc==(tr[k<<|].r-tr[k<<|].l+))

        {

             tr[k].rc=tr[k<<|].rc+tr[k<<].rc;

        }else  tr[k].rc=tr[k<<|].rc;

    }

    else

    {

        tr[k].ans=max(tr[k<<].ans,tr[k<<|].ans);

        tr[k].lc=tr[k<<].lc;

        tr[k].rc=tr[k<<|].rc;

    }

}

void build(int k,int s,int t)

{

    tr[k].l=s;

    tr[k].r=t;

    if(s==t)

    {

        tr[k].v=a[s];

        tr[k].ans=;

        tr[k].lc=;

        tr[k].rc=;

        return ;

    }

    int mid=(s+t)>>;

    build(k<<,s,mid);

    build(k<<|,mid+,t);

    push_up(k);

}

void update(int k,int x,int c)

{

    if(tr[k].l==x&&tr[k].r==x)

    {

        tr[k].v=c;

        a[x]=c;

        return ;

    }

    int mid=(tr[k].l+tr[k].r)>>;

    if(x<=mid)update(k<<,x,c);

    else update(k<<|,x,c);

    push_up(k);

}

int ask(int k,int s,int t)

{

    if(tr[k].l==s&&tr[k].r==t)

    {

        return tr[k].ans;

    }

    int mid=(tr[k].l+tr[k].r)>>;

    if(t<=mid)return ask(k<<,s,t);

    else if(s>mid)return ask(k<<|,s,t);

    else {

      int ret=;

      int A=ask(k<<,s,mid);

      int B=ask(k<<|,mid+,t);

      ret=max(A,B);

      A=min(tr[k<<].rc,mid-s+);

      B=min(tr[k<<|].lc,t-mid);

         if(a[tr[k<<].r]<a[tr[k<<|].l])

                ret=max(A+B,ret);

      return ret;

    }

}

int main()

{

    int T=read();

    while(T--)

    {

        n=read();

        q=read();

        FOR(i,,n)

        {

            a[i]=read();

        }

        build(,,n);

        int a,b;

        char ch[];

        FOR(i,,q)

        {

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

            if(ch[]=='Q')

            {

                printf("%d\n",ask(,a+,b+));

            }

            else update(,a+,b);

        }

    }

    return ;

}

代码

巴特西

HDU 3308 线段树单点更新+区间查找最长连续子序列

LCIS

最新文章

热门文章