LCIS

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

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

【题解】:

//经典线段树的应用

//难点在于Up()函数与query函数中的else

【code】:

  1 /**
  2 judge status: Accepted      exe.time:281ms
  3 exe.memory 5760k    language:C++
  4 */
  5 
  6 #include<iostream>
  7 #include<stdio.h>
  8 #include<string.h>
  9 #include<algorithm>
 10 
 11 #define N 100010
 12 #define lson p<<1
 13 #define rson p<<1|1
 14 
 15 using namespace std;
 16 
 17 struct Nod
 18 {
 19     int l,r;     //左右节点
 20     int lMax,Max,rMax;   //左边连续最长递增,整段连续最长递增,右边连续最长递增，
 21 }node[N<<2];
 22 
 23 int val[N];
 24 
 25 void Up(int p)
 26 {
 27     node[p].lMax = node[lson].lMax;
 28     node[p].rMax = node[rson].rMax;
 29     if(val[node[lson].r]<val[node[rson].l]) //如果左边的值小于右边的
 30     {
 31         if(node[lson].lMax==node[lson].r-node[lson].l+1)//如果左儿子的左边最长连续值等于整个区间，则加上右儿子的左连续区间
 32         {
 33             node[p].lMax+=node[rson].lMax;
 34         }
 35         if(node[rson].rMax==node[rson].r-node[rson].l+1)//同上
 36         {
 37             node[p].rMax+=node[lson].rMax;
 38         }
 39         //下面求整段区间的最长递增
 40         node[p].Max = max(node[p].rMax,node[p].lMax);
 41         node[p].Max = max(node[p].Max,node[lson].Max);
 42         node[p].Max = max(node[p].Max,node[rson].Max);
 43         node[p].Max = max(node[p].Max,node[lson].rMax+node[rson].lMax);
 44     }
 45     else  //否则
 46     {
 47         node[p].Max = max(node[lson].Max,node[rson].Max);   //即为左右两个区间的较大值
 48     }
 49 }
 50 
 51 void building(int l,int r,int p)  //建树
 52 {
 53     node[p].l = l;
 54     node[p].r = r;
 55     if(l==r)
 56     {
 57         node[p].lMax=node[p].rMax=node[p].Max=1;
 58         return;
 59     }
 60     int mid = (l+r)>>1;
 61     building(l,mid,lson);
 62     building(mid+1,r,rson);
 63     Up(p);
 64 }
 65 
 66 void update(int id,int v,int p)
 67 {
 68     if(node[p].l==id&&node[p].r==id)
 69     {
 70         val[id] = v;
 71         return;
 72     }
 73     int mid = (node[p].l+node[p].r)>>1;
 74     if(id<=mid) update(id,v,lson);
 75     else update(id,v,rson);
 76     Up(p);
 77 }
 78 
 79 int Query(int l,int r,int p)
 80 {
 81     if(node[p].l==l&&node[p].r==r)
 82     {
 83         return node[p].Max;
 84     }
 85     int mid = (node[p].l+node[p].r)>>1;
 86     if(r<=mid)  return Query(l,r,lson);
 87     else if(l>mid)  return Query(l,r,rson);
 88     else
 89     {
 90         int temp =  max(Query(l,mid,lson),Query(mid+1,r,rson));
 91         if(val[mid]<val[mid+1])  //分开点右边大于左边的时候则比较中间加起来是否比最大值要大。
 92         {
 93             //min(node[lson].rMax,mid-l+1); 取最小值，因为rMax可能会大于mid-l+1；
 94            temp = max(temp,min(node[lson].rMax,mid-l+1)+min(node[rson].lMax,r-mid));
 95         }
 96         return temp;
 97     }
 98 }
 99 
100 int main()
101 {
102     int t;
103     int n,m;
104     scanf("%d",&t);
105     while(t--)
106     {
107         scanf("%d%d",&n,&m);
108         int i;
109         for(i=1;i<=n;i++)   scanf("%d",val+i);
110         building(1,n,1);
111         while(m--)
112         {
113             char op[5];
114             int a,b;
115             scanf("%s%d%d",op,&a,&b);
116             if(op[0]=='U')      update(a+1,b,1);
117             else if(op[0]=='Q')     printf("%d
",Query(a+1,b+1,1));
118         }
119     }
120     return 0;
121 }