LCIS

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

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

⁵)

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

Recommend

wxl | We have carefully selected several similar problems for you:

ac代码

#include
      
       #include
       
        #define max(a,b) (a>b?

a:b) #define min(a,b) (a>b?

b:a) struct s { int lnum,rnum; int lmax,rmax,mmax; }node[1000100<<2]; void init(int tr,int num) { node[tr].lnum=num; node[tr].rnum=num; node[tr].lmax=1; node[tr].rmax=1; node[tr].mmax=1; } void pushup(int tr,int m) { node[tr].lnum=node[tr<<1].lnum; node[tr].rnum=node[tr<<1|1].rnum; node[tr].lmax=node[tr<<1].lmax; node[tr].rmax=node[tr<<1|1].rmax; node[tr].mmax=max(node[tr<<1].mmax,node[tr<<1|1].mmax); if(node[tr<<1].rnum<node[tr<<1|1].lnum) { node[tr].mmax=max(node[tr].mmax,node[tr<<1].rmax+node[tr<<1|1].lmax); if(node[tr<<1].lmax==m-(m>>1)) node[tr].lmax+=node[tr<<1|1].lmax; if(node[tr<<1|1].rmax==(m>>1)) node[tr].rmax+=node[tr<<1].rmax; } } void build(int l,int r,int tr) { if(l==r) { int num; scanf("%d",&num); init(tr,num); return; } int mid=(l+r)>>1; build(l,mid,tr<<1); build(mid+1,r,tr<<1|1); pushup(tr,r-l+1); } void update(int pos,int num,int l,int r,int tr) { if(l==r) { init(tr,num); return; } int mid=(l+r)>>1; if(pos<=mid) { update(pos,num,l,mid,tr<<1); } else update(pos,num,mid+1,r,tr<<1|1); pushup(tr,r-l+1); } int query(int L,int R,int l,int r,int tr) { if(L<=l&&R>=r) { return node[tr].mmax; } int mid=(l+r)>>1; int temp1=0,temp2=0,temp3=0; if(L<=mid) temp1=query(L,R,l,mid,tr<<1); if(R>mid) temp2=query(L,R,mid+1,r,tr<<1|1); if(L<=mid&&R>mid&&node[tr<<1].rnum<node[tr<<1|1].lnum) temp3=min(mid-L+1,node[tr<<1].rmax)+min(R-mid,node[tr<<1|1].lmax); int ans=max(temp1,max(temp2,temp3)); return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); build(1,n,1); while(m--) { char s[2]; int a,b; scanf("%s%d%d",s,&a,&b); if(s[0]=='U') { update(a+1,b,1,n,1); } else { printf("%d\n",query(a+1,b+1,1,n,1)); } } } }

转载地址：http://jbkoo.baihongyu.com/

你可能感兴趣的文章