Hdu 3308 LCIS

LCIS

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

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

Author

shǎ崽

Source

HDOJ Monthly Contest – 2010.02.06

Recommend

wxl

//经典线段树的应用

//难点在于up()函数

up()函数内容

1. 左儿子最右边的值 < 右儿子最左边的值

lMax = (左儿子的lMax == 左儿子的len) ? 左儿子的len + 右儿子的lMax : 左儿子的lMax;

rMax = (右儿子的rMax == 右儿子的len) ? 右儿子的len + 左儿子的rMax : 右儿子的rMax;

Max = MAX(左儿子的rMax + 右儿子的lMax, 左儿子的Max, 右儿子的Max, lMax, rMax);

2. 左儿子最右边的值 >= 右儿子最左边的值

lMax = 左儿子的lMax;

rMax = 右儿子的rMax;

Max = MAX(左儿子的Max, 右儿子的Max);

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define lson l,m,k<<1
#define rson m+1,r,k<<1|1
#define N 100003
using namespace std;
struct node
{
    int lmax,rmax,max;
    int lva,rva;
    int len;
};
node st[N<<3];
void up(node &k,node &ls,node &rs)
{
    k.lva=ls.lva;
    k.rva=rs.rva;
    //k.len=ls.len+rs.len;
     if(ls.rva<rs.lva)//开始这里的判断写反了、、、郁闷
     {
     k.lmax=(ls.len==ls.lmax?ls.lmax+rs.lmax:ls.lmax);
     k.rmax=(rs.len==rs.rmax?ls.rmax+rs.rmax:rs.rmax);

     k.max=max(max(k.lmax,k.rmax),ls.rmax+rs.lmax);
     k.max=max(max(ls.max,rs.max),k.max);
     }
     else
     {
         k.lmax=ls.lmax;
         k.rmax=rs.rmax;
         k.max=max(ls.max,rs.max);
     }
}
void build(int l,int r,int k)
{
    st[k].len=r-l+1;
    if(l==r)
    {
        scanf("%d",&st[k].lva);//printf("l=%d %d\n",l,st[k].lva);
        st[k].rva=st[k].lva;
        st[k].max=st[k].lmax=st[k].rmax=1;
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    int t=k<<1;
    up(st[k],st[t],st[t+1]);
}
int va;
void updata(int &index,int l,int r,int k)
{
    if(l==r)
    {
        st[k].lva=st[k].rva=va;
        //printf("%d %d %d\n",l,r,st[k].lva);
        return ;
    }
    int m=(l+r)>>1;
    if(index<=m) updata(index,lson);
    else updata(index,rson);
    int t=k<<1;
    up(st[k],st[t],st[t+1]);
}
node Query(int &L,int &R,int l,int r,int k)
{ // printf("%d %d\n",l,r);
    if(L<=l&&R>=r)
       return st[k];
    int m=(l+r)>>1;
    node r1,r2;
    r1.len=r2.len=0;
    if(L<=m) r1=Query(L,R,lson);
    if(R>m) r2=Query(L,R,rson);
    if(r1.len&&r2.len)
    {
        node temp;
        //printf("k=%d %d\n",r1.max,r2.max);
        up(temp,r1,r2);
        temp.len=r1.len+r2.len;
        return temp;
    }
       if(r1.len) return r1;
       if(r2.len) return r2;

}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,x,y;
        node te;
        char c;
        scanf("%d%d",&n,&m);
        n--;
        build(0,n,1);getchar();//坑爹的每组数据后面多了个空格、、、
      // printf("%d ",st[1].max);
        while(m--)
        {
            getchar();
            scanf("%c%d%d",&c,&x,&y);
            //printf("%c",c);
            if(c=='Q')
            {
                te=Query(x,y,0,n,1);
                printf("%d\n",te.max);
            }
            else
             va=y,updata(x,0,n,1);
        }
    }
    return 0;
}