UESTC-1425___Another LCIS —— 线段树 + 最长连续上升子序列

题目链接：点我啊╭(╯^╰)╮

题目大意：

     线段树维护 最长连续上升子序列，注意是连续

代码思路：

    $t$ —— 该区间的 最长连续上升子序列
    $lnum$ —— 左端点
    $rnum$ —— 右端点
    $lsum$ —— 以左端点为起点的 最长连续上升子序列
    $rsum$ —— 以右端点为终点的 最长连续上升子序列
??

解题思路：

    左右端点很好维护，维护上升子序列的时候，就要判断左右子树的拼接问题，用端点值进行比较，就可以判断是否可以连接起来，所以需要记录端点

    最后在查询的时候，因为左右子树也没有拼接，所以也不能直接判断，和上面也需要进行端点值比较，但是必须要注意一点，就是如果能拼接，还要注意是不是在查询的区间内，对子序列长度所在区间和查询区间进行对比，筛选，不然gg

核心：线段树维护 最长连续上升子序列 get!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 100000+10;
int t[maxn<<2],lazy[maxn<<2];
int lnum[maxn<<2], rnum[maxn<<2];
int lsum[maxn<<2], rsum[maxn<<2];void pushup(int l,int r,int rt) {lnum[rt] = lnum[rt<<1];rnum[rt] = rnum[rt<<1|1];lsum[rt] = lsum[rt<<1];rsum[rt] = rsum[rt<<1|1];t[rt] = max(t[rt<<1],t[rt<<1|1]);int leftright = rnum[rt<<1];   ///左区间的右侧数字int rightleft = lnum[rt<<1|1]; ///右区间的左侧数字int mid = (l+r)>>1;///两个区间可能拼接在一起。if(leftright<rightleft) {if(lsum[rt] == mid-l+1)lsum[rt] += lsum[rt<<1|1];if(rsum[rt] == r-mid)rsum[rt] += rsum[rt<<1];t[rt] = max(t[rt],rsum[rt<<1]+lsum[rt<<1|1]);}
}void build(int l,int r,int rt) {lazy[rt] = 0;if(l==r) {scanf("%lld",&lnum[rt]);rnum[rt] = lnum[rt];t[rt] = lsum[rt] = rsum[rt] = 1;return ;}int m = (l+r)>>1;build(lson);build(rson);pushup(l,r,rt);
}void pushdown(int rt) {if(lazy[rt]) {lazy[rt<<1] += lazy[rt];lazy[rt<<1|1] += lazy[rt];lnum[rt<<1] += lazy[rt];rnum[rt<<1] += lazy[rt];lnum[rt<<1|1] += lazy[rt];rnum[rt<<1|1] += lazy[rt];lazy[rt] = 0;}
}void update(int L,int R,int C,int l,int r,int rt) {if(L<=l&&r<=R) {lnum[rt] += C;rnum[rt] += C;lazy[rt] += C;return ;}int m = (l+r)>>1;pushdown(rt);if(L<=m) update(L,R,C,lson);if(R>m) update(L,R,C,rson);pushup(l,r,rt);
}int query(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R) return t[rt];int m = (l+r)>>1;pushdown(rt);int ans = 1;if(L<=m) ans = max(ans,query(L,R,lson));if(R>m) ans = max(ans,query(L,R,rson));if(rnum[rt<<1] < lnum[rt<<1|1]) {int rans = min(R,m+lsum[rt<<1|1]);int lans = max(L,m-rsum[rt<<1]+1); ans = max(ans,rans-lans+1);	// 注意查询区间的限制 }return ans;
}int main() {int T, n, q, Case=0;char str[10];scanf("%d", &T);while(T--) {scanf("%d%d", &n, &q);build(1,n,1);int l, r, c;printf("Case #%d:\n", ++Case);while(q--) {scanf("%s", &str);if(str[0]=='q') {scanf("%d %d", &l, &r);printf("%d\n", query(l,r,1,n,1));}if(str[0]=='a') {scanf("%d %d %d", &l, &r, &c);update(l,r,c,1,n,1);}}}
}