按照傻崽大神的线段树修炼路线，自己做的第二道区间合并的题。
问题比较简单明了，区间求最长连续上升子序列，但是是需要单点更新的
n个数， m组操作
Q A B 询问[A,B]区间的最长连续上升子序列；
O A B 把位置为A的数字改成B。(位置从0开始)
LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4291 Accepted Submission(s): 1958 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
Author
shǎ崽
线段树上的每个节点记录的信息有：
1.左右两端的端点值(用于鉴定左右两个区间能否合并)
2.左、右儿子的最长连续上升子序列长度，总区间的最长连续上升子序列长度。 PS：查询的时候需要判断下区间长度和连续的长度哪个小，以免连续长度超过区间长度。
#include#include #include #include #include using namespace std;#define LL(x) (x << 1)#define RR(x) (x << 1 | 1)#define MID(x, y) (x + ((y - x) >> 1))#define lson l, mid, LL(t)#define rson mid + 1, r, RR(t)const int MAXN = 100100;int t, n, m;int a[MAXN];struct node { int lmx, rmx, mx;//左、右和总体最长公共上升子序列长度 int lp, rp;//左右端点值};class segment_tree { public: node tree[MAXN << 2]; int point[MAXN << 2]; void pushup(int t) { tree[t].lp = tree[LL(t)].lp; tree[t].rp = tree[RR(t)].rp; tree[t].lmx = tree[LL(t)].lmx; tree[t].rmx = tree[RR(t)].rmx; tree[t].mx = max(tree[LL(t)].mx, tree[RR(t)].mx); if(tree[LL(t)].rp < tree[RR(t)].lp) { tree[t].mx = max(tree[t].mx, tree[LL(t)].rmx + tree[RR(t)].lmx); if(tree[LL(t)].lmx == point[LL(t)]) tree[t].lmx = tree[LL(t)].lmx + tree[RR(t)].lmx; if(tree[RR(t)].rmx == point[RR(t)]) tree[t].rmx = tree[RR(t)].rmx + tree[LL(t)].rmx; } tree[t].mx = max(tree[t].mx, max(tree[t].lmx, tree[t].rmx)); } void build(int l, int r, int t) { if(l == r) { tree[t].lp = tree[t].rp = a[l]; tree[t].lmx = tree[t].rmx = tree[t].mx = 1; point[t] = 1; } else { int mid = MID(l, r); build(lson); build(rson); point[t] = point[LL(t)] + point[RR(t)]; pushup(t); } } int query(int st, int ed, int l, int r, int t) { if(st <= l && r <= ed) return tree[t].mx; else { int mid = MID(l, r); if(ed <= mid) return query(st, ed, lson); else if(st > mid) return query(st, ed, rson); else { int temp1 = 0, temp2 = 0; int mx1 = query(st, ed, lson); int mx2 = query(st, ed, rson); if(tree[LL(t)].rp < tree[RR(t)].lp) { temp1 = min(mid - st + 1, tree[LL(t)].rmx); temp2 = min(ed - mid, tree[RR(t)].lmx); } return max(max(mx1 , mx2), temp1 + temp2); } } } void update(int pos, int l, int r, int t, int w) { if(l == r) tree[t].lp = tree[t].rp = w; else { int mid = MID(l, r); if(pos <= mid) update(pos, lson, w); else update(pos, rson, w); pushup(t); } }}seg;int main() { scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); memset(a, 0, sizeof(a)); for(int i = 0; i < n; i++) scanf("%d", &a[i]); seg.build(0, n - 1, 1); char ch[2]; int x, y; while(m--) { scanf("%s%d%d", ch, &x, &y); if(ch[0] == 'Q') { printf("%d\n", seg.query(x, y, 0, n - 1, 1)); } else { seg.update(x, 0, n - 1, 1, y); } } } return 0;}