HDU 3308 LCIS

LCIS

Time Limit: 2000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3308
64-bit integer IO format: %I64d Java class name: Main

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

解题思路：线段树的区间合并。哎。。。写了三四遍才过的！！！！！！！！int lt,rt,lx,rx,mx,wth;依次为左边界，右边界，左上升区间长度，右上升区间长度，lt rt中的最大上升区间长度。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int maxn = 100010;
 5 struct node{
 6     int lt,rt,lx,rx,mx,wth;
 7 }tree[maxn<<2];
 8 int d[maxn];
 9 void fix(int v,int mid){
10     tree[v].lx = tree[v<<1].lx;
11     tree[v].rx = tree[v<<1|1].rx;
12     if(d[mid] < d[mid+1]){
13         tree[v].lx += tree[v].lx == tree[v<<1].wth?tree[v<<1|1].lx:0;
14         tree[v].rx += tree[v].rx == tree[v<<1|1].wth?tree[v<<1].rx:0;
15         tree[v].mx = max(tree[v<<1].mx,tree[v<<1|1].mx);
16         tree[v].mx = max(tree[v].mx,tree[v<<1].rx+tree[v<<1|1].lx);
17     }else tree[v].mx = max(tree[v<<1].mx,tree[v<<1|1].mx);
18 }
19 void build(int lt,int rt,int v){
20     tree[v].lt = lt;
21     tree[v].rt = rt;
22     tree[v].wth = rt-lt+1;
23     if(lt == rt){tree[v].lx = tree[v].rx = tree[v].mx = 1;return;}
24     int mid = (lt+rt)>>1;
25     build(lt,mid,v<<1);
26     build(mid+1,rt,v<<1|1);
27     fix(v,mid);
28 }
29 void update(int u,int val,int v){
30     int mid = (tree[v].lt+tree[v].rt)>>1;
31     if(tree[v].lt == tree[v].rt) {d[tree[v].lt] = val;return;}
32     if(u <= mid) update(u,val,v<<1);
33     else update(u,val,v<<1|1);
34     fix(v,mid);
35 }
36 int query(int lt,int rt,int v){
37     if(tree[v].lt == lt && tree[v].rt == rt) return tree[v].mx;
38     int mid = (tree[v].lt+tree[v].rt)>>1;
39     if(rt <= mid) return query(lt,rt,v<<1);
40     else if(lt > mid) return query(lt,rt,v<<1|1);
41     else{
42         int temp = max(query(lt,mid,v<<1),query(mid+1,rt,v<<1|1));
43         if(d[mid] < d[mid+1]){
44             temp = max(min(mid-lt+1,tree[v<<1].rx)+min(rt-mid,tree[v<<1|1].lx),temp);
45             //看看合并是否可以使取值更优
46         }
47         return temp;
48     }
49 }
50 int main(){
51     int ks,n,m,i,x,y;
52     char op[5];
53     scanf("%d",&ks);
54     while(ks--){
55         scanf("%d %d",&n,&m);
56         for(i = 1; i <= n; i++)
57             scanf("%d",d+i);
58             build(0,n,1);
59         for(i = 0; i < m; i++){
60             scanf("%s%d%d",op,&x,&y);
61             if(op[0] == 'Q'){
62                 printf("%d
",query(x+1,y+1,1));
63             }else update(x+1,y,1);
64         }
65     }
66     return 0;
67 }

View Code