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].
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).
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
Author
shǎ崽
Source
Recommend
ac代码
#include<stdio.h>
#include<string.h>
#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));
}
}
}
}