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^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
数据结构-区间合并线段树
区间合并，将最长连续序列由其左右子区间的关系得出
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Segtree{
int l,r,len;
int maxn;
int lmax;
int rmax;
}tr[N<<2];
int w[N];
void pushup(int rt)
{
auto &s=tr[rt];
auto &a=tr[rt<<1];
auto &b=tr[rt<<1|1];
s.l=a.l;
s.r=b.r;
s.len=a.len+b.len;
if(w[a.r]>=w[b.l])
{
s.lmax=a.lmax;
s.rmax=b.rmax;
s.maxn=max(a.maxn,b.maxn);//注意此处应该为左右子树LCIS的max值
}
else
{
s.lmax=(a.lmax==a.len)?a.len+b.lmax:a.lmax;
s.rmax=(b.rmax==b.len)?b.len+a.rmax:b.rmax;
s.maxn=max(a.maxn,max(a.rmax+b.lmax,b.maxn));
}
}
void build(int l,int r,int rt)
{
auto &s=tr[rt];
if(l==r)
{
s.l=s.r=l;
s.lmax=s.rmax=s.maxn=s.len=1;
return ;
}
int m=(l+r)>>1;
build(l,m,rt<<1);build(m+1,r,rt<<1|1);
pushup(rt);
}
void update(int t,int l,int r,int rt)
{
auto &s=tr[rt];
if(l==r) return ;
int m=(l+r)>>1;
if(t<=m) update(t,l,m,rt<<1);
else update(t,m+1,r,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
auto &s=tr[rt];
auto &a=tr[rt<<1];
auto &b=tr[rt<<1|1];
int ans=0;
if(L>r||R<l) return 0;
if(L<=l&&R>=r) return s.maxn;
int m=(l+r)>>1;
if(L<=m) ans=max(ans,query(L,R,l,m,rt<<1));
if(R>m) ans=max(ans,query(L,R,m+1,r,rt<<1|1));
if(L<=m&&R>m&&w[a.r]<w[b.l])
ans=max(ans,min(a.rmax,m-L+1)+min(b.lmax,R-m));
return ans;
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>w[i];
build(1,n,1);
for(int i=0;i<m;++i)
{
char op;
cin>>op;
int p,q;
cin>>p>>q;
if(op=='Q')
{
cout<<query(p+1,q+1,1,n,1)<<'\n';
}
else
{
w[p+1]=q;
update(p+1,1,n,1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}