LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3392 Accepted Submission(s): 1510
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<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=110500;
int lsum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];
int arr[maxn];
void push_up(int l,int r,int rt)
{
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
int m=(r+l)>>1;
if(arr[m]<arr[m+1])
{
if(lsum[rt<<1]==m-l+1)
lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt<<1|1]==r-m)
rsum[rt]+=rsum[rt<<1];
sum[rt]=max(sum[rt],rsum[rt<<1]+lsum[rt<<1|1]);
}
}
void build(int l,int r,int rt)
{
if(l==r)
{
lsum[rt]=rsum[rt]=sum[rt]=1;
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(l,r,rt);
}
void update(int l,int r,int rt,int P,int V)
{
if(l==r)
{
arr[P]=V;
return ;
}
int m=(l+r)>>1;
if(P<=m) update(lson,P,V);
else update(rson,P,V);
push_up(l,r,rt);
}
int query(int l,int r,int rt,int L,int R)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int ret=0;
int m=(l+r)>>1;
if(L<=m) ret=max(ret,query(lson,L,R));
if(R>m) ret=max(ret,query(rson,L,R));
if(arr[m]<arr[m+1]&&L<=m&&R>m)
{
ret=max(ret,min(m-L+1,rsum[rt<<1])+min(R-m,lsum[rt<<1|1]));
}
return ret;
}
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--)
{
memset(lsum,0,sizeof(lsum));
memset(rsum,0,sizeof(rsum));
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",arr+i);
}
build(1,n,1);
while(m--)
{
char cmd[10];
int a,b;
scanf("%s%d%d",cmd,&a,&b);
if(cmd[0]==‘Q‘)
{
printf("%d\n",query(1,n,1,a+1,b+1));
}
else if(cmd[0]==‘U‘)
{
update(1,n,1,a+1,b);
}
}
}
return 0;
}