题目链接
题目大意
查询区间中最长的连续上升序列，支持单点修改。
题目思路
线段树合并的题目，感觉有点小怪
记录区间中以左边界为起点的答案，和右边界为终点的答案，还有区间总答案
查询的时候也不是普通查询
这个题目记录下
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int a[maxn];
int mal[maxn],mar[maxn],ma[maxn];
void pushup(int node,int l,int r){
mal[node]=mal[node<<1];
mar[node]=mar[node<<1|1];
ma[node]=max(ma[node<<1],ma[node<<1|1]);
int mid=(l+r)/2;
if(a[mid]<a[mid+1]){
if(mal[node<<1]==mid-l+1){
mal[node]+=mal[node<<1|1];
}
if(mar[node<<1|1]==r-mid){
mar[node]+=mar[node<<1];
}
ma[node]=max(ma[node],mar[node<<1]+mal[node<<1|1]);
}
}
void build(int node,int l,int r){
if(l==r){
mal[node]=mar[node]=ma[node]=1;
return ;
}
int mid=(l+r)/2;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
pushup(node,l,r);
}
void update(int node,int pos,int val,int l,int r){
if(l==r){
return ;
}
int mid=(l+r)/2;
if(mid>=pos) update(node<<1,pos,val,l,mid);
else update(node<<1|1,pos,val,mid+1,r);
pushup(node,l,r);
}
int query(int node,int L,int R,int l,int r){
if(L<=l&&r<=R){
return ma[node];
}
int mid=(l+r)/2,ans=0;
if(mid>=L) ans=max(ans,query(node<<1,L,R,l,mid));
if(mid<R) ans=max(ans,query(node<<1|1,L,R,mid+1,r));
// 注意
if(a[mid]<a[mid+1]){
ans=max(ans,min(mid-L+1,mar[node<<1])+min(R-mid,mal[node<<1|1]));
}
return ans;
}
int main(){
int _; cin>>_;
while(_--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
char opt;
for(int i=1,x,y;i<=m;i++){
getchar();
cin>>opt>>x>>y;
if(opt==‘Q‘){
x++,y++;
cout<<query(1,x,y,1,n)<<‘\n‘;
}else{
x++;
a[x]=y;
update(1,x,y,1,n);
}
}
}
return 0;
}