LCIS

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

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

Source

HDOJ Monthly Contest – 2010.02.06

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

const int N=1e5+,M=4e6+,inf=1e9+;

struct is

{

    int l,r;

    int lm,mm,rm;

}tree[N<<];

int val[N];

void buildtree(int l,int r,int pos)

{

    tree[pos].l=l;

    tree[pos].r=r;

    if(l==r)

    {

        tree[pos].lm=tree[pos].rm=tree[pos].mm=;

        return;

    }

    int mid=(l+r)>>;

    buildtree(l,mid,pos<<);

    buildtree(mid+,r,pos<<|);

    tree[pos].lm=tree[pos<<].lm;

    tree[pos].rm=tree[pos<<|].rm;

    if(val[tree[pos<<].r]<val[tree[pos<<|].l])

    tree[pos].mm=max(tree[pos<<].mm,max(tree[pos<<|].mm,tree[pos<<].rm+tree[pos<<|].lm));

    else

    tree[pos].mm=max(tree[pos<<].mm,tree[pos<<|].mm);

    if(val[tree[pos<<].r]<val[tree[pos<<|].l]&&tree[pos<<].lm==tree[pos<<].r-tree[pos<<].l+)

    tree[pos].lm+=tree[pos<<|].lm;

    if(val[tree[pos<<].r]<val[tree[pos<<|].l]&&tree[pos<<|].rm==tree[pos<<|].r-tree[pos<<|].l+)

    tree[pos].rm+=tree[pos<<].rm;

}

void update(int point,int pos)

{

    if(tree[pos].l==tree[pos].r)

    return;

    int mid=(tree[pos].r+tree[pos].l)>>;

    if(point>mid)

    update(point,pos<<|);

    else

    update(point,pos<<);

    tree[pos].lm=tree[pos<<].lm;

    tree[pos].rm=tree[pos<<|].rm;

    if(val[tree[pos<<].r]<val[tree[pos<<|].l])

    tree[pos].mm=max(tree[pos<<].mm,max(tree[pos<<|].mm,tree[pos<<].rm+tree[pos<<|].lm));

    else

    tree[pos].mm=max(tree[pos<<].mm,tree[pos<<|].mm);

    if(val[tree[pos<<].r]<val[tree[pos<<|].l]&&tree[pos<<].lm==tree[pos<<].r-tree[pos<<].l+)

    tree[pos].lm+=tree[pos<<|].lm;

    if(val[tree[pos<<].r]<val[tree[pos<<|].l]&&tree[pos<<|].rm==tree[pos<<|].r-tree[pos<<|].l+)

    tree[pos].rm+=tree[pos<<].rm;

}

is query(int L,int R,int pos)

{

    if(tree[pos].l==L&&tree[pos].r==R)

    return tree[pos];

    int mid=(tree[pos].l+tree[pos].r)>>;

    if(mid<L)

    return query(L,R,pos<<|);

    else if(mid>=R)

    return query(L,R,pos<<);

    else

    {

        is a=query(L,mid,pos<<);

        is b=query(mid+,R,pos<<|);

        is ans;

        ans.l=a.l,ans.r=b.r;

        ans.lm=a.lm;

        ans.rm=b.rm;

        if(val[a.r]<val[b.l])

        ans.mm=max(a.mm,max(b.mm,a.rm+b.lm));

        else

        ans.mm=max(a.mm,b.mm);

        if(val[a.r]<val[b.l]&&a.lm==a.r-a.l+)

        ans.lm+=b.lm;

        if(val[a.r]<val[b.l]&&b.rm==b.r-b.l+)

        ans.rm+=a.rm;

        return ans;

    }

}

char a[];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

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

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

        scanf("%d",&val[i]);

        buildtree(,n,);

        while(m--)

        {

            int l,r;

            scanf("%s%d%d",a,&l,&r);

            l++;

            if(a[]=='U')

            val[l]=r,update(l,);

            else

            r++,printf("%d\n",query(l,r,).mm);

            }

    }

    return ;

}

巴特西

hdu 3308 线段树区间合并+单点更新+区间查询

LCIS

最新文章

热门文章

巴特西

hdu 3308 线段树 区间合并+单点更新+区间查询

LCIS

最新文章

热门文章

hdu 3308 线段树区间合并+单点更新+区间查询