题意：线段树操作：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 <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
struct ST {
struct Node {
int lx, rx;
int ls, rs, ms;
}node[N<<2];
void push_up(int l, int r, int rt) {
node[rt].ls = node[rt<<1].ls; node[rt].rs = node[rt<<1|1].rs;
node[rt].lx = node[rt<<1].lx; node[rt].rx = node[rt<<1|1].rx;
node[rt].ms = max (node[rt<<1].ms, node[rt<<1|1].ms);
int mid = (l + r) >> 1;
if (node[rt<<1].rx < node[rt<<1|1].lx) {
if (node[rt<<1].ls == mid - l + 1) {
node[rt].ls += node[rt<<1|1].ls;
}
if (node[rt<<1|1].rs == r - mid) {
node[rt].rs += node[rt<<1].rs;
}
node[rt].ms = max (node[rt].ms, node[rt<<1].rs + node[rt<<1|1].ls);
}
}
void build(int l, int r, int rt) {
if (l == r) {
scanf ("%d", &node[rt].lx);
node[rt].rx = node[rt].lx;
node[rt].ls = node[rt].rs = node[rt].ms = 1;
return ;
}
int mid = (l + r) >> 1;
build (lson); build (rson);
push_up (l, r, rt);
}
void updata(int p, int c, int l, int r, int rt) {
if (l == r) {
node[rt].lx = node[rt].rx = c; return ;
}
int mid = (l + r) >> 1;
if (p <= mid) updata (p, c, lson);
else updata (p, c, rson);
push_up (l, r, rt);
}
int query(int ql, int qr, int l, int r, int rt) {
if (ql <= l && r <= qr) {
return node[rt].ms;
}
int mid = (l + r) >> 1, ret = 0;
if (ql <= mid) {
ret = max (ret, query (ql, qr, lson));
}
if (qr > mid) {
ret = max (ret, query (ql, qr, rson));
}
if (node[rt<<1].rx < node[rt<<1|1].lx) {
ret = max (ret, min (mid - ql + 1, node[rt<<1].rs) + min (qr - mid, node[rt<<1|1].ls));
}
return ret;
}
}st; int main(void) {
int T; scanf ("%d", &T);
while (T--) {
int n, q; scanf ("%d%d", &n, &q);
st.build (1, n, 1);
for (int a, b, i=1; i<=q; ++i) {
char s[2]; scanf ("%s%d%d", &s, &a, &b);
if (s[0] == 'Q') {
printf ("%d\n", st.query (a + 1, b + 1, 1, n, 1));
}
else {
st.updata (a + 1, b, 1, n, 1);
}
}
} return 0;
}
新代码
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 1e5 + 5; #define lc o << 1
#define rc o << 1 | 1 int 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;
}