题意:线段树操作:1. 单点更新 2. 求区间的LCIS(longest consecutive increasing subsequence)
分析:注意是连续的子序列,就是简单的区间合并,记录线段的端点的值,如果rx[rt<<1] < lx[rt<<1|1]就区间合并,最后结果保存在ms中。因为记录的数据较多,索性结构体内再开一个结构体,感觉还不错。写完这题,对区间合并的操作有了更深的理解。
/************************************************* Author :Running_Time* Created Time :2015/9/25 星期五 10:37:34* File Name :G.cpp ************************************************/#include#include #include #include #include #include #include #include #include #include #include #include #include
新代码
#includeusing namespace std;typedef long long ll;const int N = 1e5 + 5;#define lc o << 1#define rc o << 1 | 1int s[N<<2], sl[N<<2], sr[N<<2];int al[N<<2], ar[N<<2];int x[N];void push_up(int o, int l, int r) { sl[o] = sl[lc]; sr[o] = sr[rc]; al[o] = al[lc]; ar[o] = ar[rc]; s[o] = max(s[lc], s[rc]); int mid = l + r >> 1; if (ar[lc] < al[rc]) { s[o] = max(s[o], sr[lc]+sl[rc]); if (sl[o] == mid-l+1) sl[o] += sl[rc]; if (sr[o] == r-mid) sr[o] += sr[lc]; }}void build(int o, int l, int r) { if (l == r) { al[o] = ar[o] = x[l]; s[o] = sl[o] = sr[o] = 1; return ; } int mid = l + r >> 1; build(lc, l, mid); build(rc, mid+1, r); push_up(o, l, r);}void modify(int o, int l, int r, int p, int v) { if (l == r) { al[o] = ar[o] = v; return ; } int mid = l + r >> 1; if (p <= mid) modify(lc, l, mid, p, v); else modify(rc, mid+1, r, p, v); push_up(o, l, r);}int query(int o, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return s[o]; int mid = l + r >> 1, ret = 0; if (ql <= mid) ret = max(ret, query(lc, l, mid, ql, qr)); if (qr > mid) ret = max(ret, query(rc, mid+1, r, ql, qr)); if (ql <= mid && qr > mid) { if (ar[lc] < al[rc]) { ret = max(ret, min(sr[lc], mid-ql+1)+min(sl[rc], qr-mid)); } } return ret;}int main() { int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d%d", &n, &m); for (int i=1; i<=n; ++i) { scanf("%d", &x[i]); } build(1, 1, n); char str[5]; int a, b; while (m--) { scanf("%s%d%d", &str, &a, &b); if (str[0] == 'U') modify(1, 1, n, a+1, b); else printf("%d\n", query(1, 1, n, a+1, b+1)); } } return 0;}