LCIS
Time Limit : 6000/2000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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 5).
The next line has n integers(0<=val<=10 5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10 5)
OR
Q A B(0<=A<=B< n).
Each case starts with two integers n , m(0<n,m<=10 5).
The next line has n integers(0<=val<=10 5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10 5)
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
HDOJ Monthly Contest – 2010.02.06
#include <queue>
#include <iostream>
#include<cstring>
#include<stdio.h>
#define maxn 100050
using namespace std;
int n,m,x,y;
char c;
/*
区间合并；
该程序没有剪枝就过了，估计是数据水吧。。。
如果有两个区间，如何设定标准值并进行操作把它合并成一个区间呢。
首先肯定需要两个子区间的最长长度，
然后对大区间的中间部分进行判定，
依次递推下标。。。得到另外一个判断值，再代入比较
*/
struct node
{int l,r;int v,maxl;//最长长度int lc,rc;node(){lc=rc=0;l=r=v=maxl=0;}
};
node seq[maxn<<2];
int num[maxn];void pushup(int rt)
{int rr=seq[rt<<1].r,ll=seq[rt<<1|1].l;int nlc,nrc,tmp;seq[rt].maxl=max(seq[rt<<1].maxl,seq[rt<<1|1].maxl);if(seq[rt].maxl==seq[rt<<1].maxl){seq[rt].lc=seq[rt<<1].lc,seq[rt].rc=seq[rt<<1].rc;}else if(seq[rt].maxl==seq[rt<<1|1].maxl){seq[rt].lc=seq[rt<<1|1].lc,seq[rt].rc=seq[rt<<1|1].rc;}if(num[ll]>num[rr]){nlc=rr,nrc=ll;while(nrc+1<=seq[rt<<1|1].r&&num[nrc]<num[nrc+1])nrc++;while(nlc-1>=seq[rt<<1].l&&num[nlc]>num[nlc-1])nlc--;seq[rt].maxl=max(seq[rt].maxl,nrc-nlc+1);if(seq[rt].maxl==nrc-nlc+1)seq[rt].lc=nlc,seq[rt].rc=nrc;}
}void build(int l,int r,int rt)
{seq[rt].l=l;seq[rt].r=r;if(l==r){seq[rt].lc=seq[rt].rc=l;seq[rt].v=num[l];seq[rt].maxl=1;return ;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);
}void update(int p,int rt,int val)
{if(seq[rt].l==seq[rt].r){seq[rt].v=num[seq[rt].l]=val ;return ;}int mid=(seq[rt].l+seq[rt].r)>>1;if(mid>=p) update(p,rt<<1,val);else update(p,rt<<1|1,val);pushup(rt);
}int query(int l,int r,int rt)
{if(seq[rt].l>=l&&seq[rt].r<=r)return seq[rt].maxl;int mid=(seq[rt].l+seq[rt].r)>>1;int max1=0,max2=0,maxx=-1;int nl=0,nr=0;if(mid>=l)max1=query(l,r,rt<<1);if(r>mid)max2=query(l,r,rt<<1|1);maxx=max(max1,max2);if(max1&&max2){nl=mid,nr=mid+1;if(num[nl]<num[nr]){while(nr+1<=r&&num[nr]<num[nr+1])nr++;while(nl-1>=l&&num[nl]>num[nl-1])nl--;}elsenl=nr=0;}return max(maxx,nr-nl+1);
}int main()
{ios::sync_with_stdio(false);int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&num[i]);getchar();build(1,n,1);while(m--){//scanf("%c",&c);cin>>c;if(c=='U'){cin>>x>>y;//scanf("%d%d",&x,&y);x++;update(x,1,y);}else{cin>>x>>y;//scanf("%d%d",&x,&y);x++,y++;cout<<query(x,y,1)<<endl;}}}return 0;
}