本文共 3340 字，大约阅读时间需要 11 分钟。
题意：单点更新，区间LCIS(最长连续递增序列)查询。具备区间合并维护的性质，不用线段树用什么~
1 #pragma comment(linker, "/STACK:10240000,10240000") 2 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 17 using namespace std; 18 19 #define mem0(a) memset(a, 0, sizeof(a)) 20 #define lson l, m, rt << 1 21 #define rson m + 1, r, rt << 1 | 1 22 #define define_m int m = (l + r) >> 1 23 #define Rep(a, b) for(int a = 0; a < b; a++) 24 #define lowbit(x) ((x) & (-(x))) 25 #define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {} 26 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {} 27 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {} 28 29 typedef double db; 30 typedef long long LL; 31 typedef pair pii; 32 typedef multiset msi; 33 typedef multiset ::iterator msii; 34 typedef set si; 35 typedef set ::iterator sii; 36 typedef vector vi; 37 38 const int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1}; 39 const int dy[8] = { 0, -1, 0, 1, -1, 1, 1, -1}; 40 const int maxn = 1e5 + 7; 41 const int maxm = 1e5 + 7; 42 const int maxv = 1e7 + 7; 43 const int MD = 1e9 +7; 44 const int INF = 1e9 + 7; 45 const double PI = acos(-1.0); 46 const double eps = 1e-10; 47 48 int A[maxn]; 49 50 struct SegTree { 51 struct Node { 52 int suflen, prelen, len; 53 } tree[maxn << 2]; 54 55 Node merge(Node a, Node b, int l, int m, int r) { 56 Node c; 57 int leftLen = m - l + 1, rightLen = r - m; 58 c.prelen = a.prelen; 59 if (c.prelen == leftLen && A[m] < A[m + 1]) c.prelen += b.prelen; 60 c.suflen = b.suflen; 61 if (c.suflen == rightLen && A[m] < A[m + 1]) c.suflen += a.suflen; 62 c.len = a.len; 63 c.len = max(c.len, b.len); 64 if (A[m] < A[m + 1])c.len = max(c.len, a.suflen + b.prelen); 65 return c; 66 } 67 void build(int l, int r, int rt) { 68 if (l == r) { 69 int x; 70 scanf("%d", &x); 71 A[l] = x; 72 tree[rt].len = tree[rt].prelen = tree[rt].suflen = 1; 73 return ; 74 } 75 define_m; 76 build(lson); 77 build(rson); 78 tree[rt] = merge(tree[rt << 1], tree[rt << 1 | 1], l, m, r); 79 } 80 void update(int p, int x, int l, int r, int rt) { 81 if (l == r) { 82 tree[rt].len = tree[rt].prelen = tree[rt].suflen = 1; 83 A[l] = x; 84 return ; 85 } 86 define_m; 87 if (p <= m) update(p, x, lson); 88 else update(p, x, rson); 89 tree[rt] = merge(tree[rt << 1], tree[rt << 1 | 1], l, m, r); 90 } 91 Node query(int L, int R, int l, int r, int rt) { 92 if (L <= l && r <= R) return tree[rt]; 93 define_m; 94 if (R <= m) return query(L, R, lson); 95 if (L > m) return query(L, R, rson); 96 return merge(query(L, m, lson), query(m + 1, R, rson), L, m, R); 97 } 98 }; 99 100 SegTree st;101 102 int main() {103 //freopen("in.txt", "r", stdin);104 int T;105 cin >> T;106 while (T--) {107 int n, m;108 cin >> n >> m;109 st.build(1, n, 1);110 for (int i = 0, u, v; i < m; i++) {111 char s[3];112 scanf("%s%d%d", s, &u, &v);113 if (s[0] == 'U') {114 st.update(++u, v, 1, n, 1);115 }116 else {117 printf("%d\n", st.query(++u, ++v, 1, n, 1).len);118 }119 }120 }121 return 0;122 }
转载于:https://www.cnblogs.com/jklongint/p/4418997.html
