LCIS

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

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

 

 

题解：

给你n个数组成的序列（序列中编号从0到n-1），有q次操作。

操作1——Q a  b，让你输出区间[a, b]里面最长的连续递增序列的长度；

操作2——U a  b，修改序列第a个数为b。

出了点小问题错了半天；

刚开始理解错了，是单调上升序列；1 3 5 7也算；

区间合并

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int INF=0x3f3f3f3f;#define mem(x,y) memset(x,y,sizeof(x))#define SI(x) scanf("%d",&x)#define PI(x) printf("%d",x)#define SD(x,y) scanf("%lf%lf",&x,&y)#define P_ printf(" ")#define ll root<<1#define rr root<<1|1#define lson ll,l,mid#define rson rr,mid+1,rtypedef long long LL;const int MAXN=100010;struct Node{ int len,lv,rv,lsum,rsum,sum; Node init(int l,int r){ scanf("%d",&lv);rv=lv; lsum=sum=rsum=1; }};Node tree[MAXN<<2];/*void print(int root,int l,int r){ int mid=(l+r)>>1; if(l==r){ printf("%d %d\n",tree[root].lv,tree[root].rv);return; } print(lson);print(rson);}*/void pushup(int root){ tree[root].lsum=tree[ll].lsum; tree[root].rsum=tree[rr].rsum; tree[root].lv=tree[ll].lv; tree[root].rv=tree[rr].rv; tree[root].sum=max(tree[ll].sum,tree[rr].sum); if(tree[ll].rv
            
             >1; build(lson); build(rson); pushup(root);}void update(int root,int l,int r,int A,int B){ int mid=(l+r)>>1; if(l==A&&r==A){ tree[root].lv=tree[root].rv=B; return; } if(mid>=A)update(lson,A,B); else update(rson,A,B); pushup(root);}int query(int root,int l,int r,int A,int B){ if(l>=A&&r<=B)return tree[root].sum; int mid=(l+r)>>1; int ans=0; if(mid>=A)ans=max(ans,query(lson,A,B));//多加了return错了半天；；；； if(mid