题目大意：给你n个数，m个操作。
有两种操作：
1.U x y 将数组第x位变为y
2. Q x y 问数组第x位到第y位连续最长子序列的长度。
对于每次询问，输出连续最长子序列的长度
思路：用线段树维护上升序列，每个端点维护：左边连续递增的len，右边连续递增的len，中间连续递增的len，左边val，右边val，和目前的len。然后不断更新即可。
注意：如果左区间的最右边的值小于右区间最左边的值，则有一个待定答案是左儿子的右区间+右儿子的左区间
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") /* ①记录本身内部的序列长度 ②要将区间合并的时候，rightson的left区间和leftson的right区间判断条件以后再合并。 如果合并区间是对于两端的值 */ const int maxn = 1e5 + 5; struct Tree{ int leftlen, rightlen, midlen, leftval, rightval, len; }tree[maxn << 2]; int n, m; inline void pushup(int o){ int lb = o << 1, rb = o << 1 | 1; int lbval = tree[lb].rightval, rbval = tree[rb].leftval; bool flag = false; tree[o].midlen = max(tree[lb].rightlen, max(tree[rb].leftlen, max(tree[lb].midlen, tree[rb].midlen))); if (lbval < rbval) { flag = true; tree[o].midlen = max(tree[lb].rightlen + tree[rb].leftlen, tree[o].midlen); } tree[o].leftlen = tree[lb].leftlen; if (tree[lb].rightlen == tree[lb].len && flag) tree[o].leftlen = tree[o].midlen; tree[o].rightlen = tree[rb].rightlen; if (tree[rb].leftlen == tree[rb].len && flag) tree[o].rightlen = tree[o].midlen; tree[o].leftval = tree[lb].leftval, tree[o].rightval = tree[rb].rightval; } void buildtree(int l, int r, int o){ tree[o].len = r - l + 1; if (l == r){ int val; scanf("%d", &val); tree[o].leftlen = tree[o].rightlen = tree[o].midlen = 1; tree[o].leftval = tree[o].rightval = val; return ; } int mid = (l + r) / 2; if (l <= mid) buildtree(l, mid, o << 1); if (r > mid) buildtree(mid + 1, r, o << 1 | 1); pushup(o); //printf("l = %d r = %d leftlen = %d rightlen = %d midlen = %d ", l, r, tree[o].leftlen, tree[o].rightlen, tree[o].midlen); } void update(int pos, int val, int l, int r, int o){ if (pos == l && pos == r){ tree[o].leftval = tree[o].rightval = val; return ; } int mid = (l + r) / 2; if (pos <= mid) update(pos, val, l, mid, o << 1); if (pos > mid) update(pos, val, mid + 1, r, o << 1 | 1); pushup(o); } int query(int ql, int qr, int l, int r, int o){ int ans = 1; if (ql <= l && qr >= r){ ans = max(ans, max(tree[o].leftlen, max(tree[o].rightlen, tree[o].midlen))); return ans; } int mid = (l + r) / 2; int t1 = -1, t2 = -1; if (mid >= ql){ t1 = query(ql, qr, l, mid, o << 1); } if (mid < qr){ t2 = query(ql, qr, mid + 1, r, o << 1 | 1); } ans = max(ans, max(t1, t2)); ///如果左区间的最右边的值小于右区间最左边的值，则有一个待定答案是左儿子的右区间+右儿子的左区间 if (tree[o << 1].rightval < tree[o << 1 | 1].leftval && t1 > 0 && t2 > 0){ t1 = min(tree[o << 1].rightlen, mid - ql + 1) + min(tree[o << 1 | 1].leftlen, qr - mid); ans = max(ans, t1); } return ans; } int main(){ int t; cin >> t; while (t--){ scanf("%d%d", &n, &m); buildtree(1, n, 1); for (int i = 1; i <= m; i++){ char ch[2]; int a, b; scanf("%s%d%d", ch, &a, &b); if (ch[0] == 'U'){ update(a + 1, b, 1, n, 1); } else { printf("%d ", query(a + 1, b + 1, 1, n, 1)); } } } return 0; }
关键：
感觉和以前的一题CF很像，忘了是哪里的了......