首页 > 代码库 > HDU 3308 LCIS（线段树）

HDU 3308 LCIS（线段树）

2024-07-02 15:07:06   232人阅读

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<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
 
Output
For each Q, output the answer.
 
题目大意：给n个数，动态地修改某个数的值，或者查询一段区间的LCIS（最长连续上升子序列，坑爹的标题……）。
思路：线段树，每个点维护一个区间的从左边开始的最长的LCIS，从右边开始的最长的LCIS，这个区间最大的LCIS。然后随便搞搞就能过了……
 
代码（593MS）：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 100010 << 2;
 8 
 9 int lmax[MAXN], rmax[MAXN], mmax[MAXN];
10 int a[MAXN], n, m, T;
11 
12 void update(int x, int l, int r, int pos, int val) {
13     if(pos <= l && r <= pos) {
14         a[pos] = val;
15     } else {
16         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
17         if(pos <= mid) update(ll, l, mid, pos, val);
18         if(mid < pos) update(rr, mid + 1, r, pos, val);
19         if(a[mid] < a[mid + 1]) {
20             lmax[x] = lmax[ll] + (lmax[ll] == mid - l + 1) * lmax[rr];
21             rmax[x] = rmax[rr] + (rmax[rr] == r - mid) * rmax[ll];
22             mmax[x] = max(rmax[ll] + lmax[rr], max(mmax[ll], mmax[rr]));
23         } else {
24             lmax[x] = lmax[ll];
25             rmax[x] = rmax[rr];
26             mmax[x] = max(mmax[ll], mmax[rr]);
27         }
28     }
29 }
30 
31 int query(int x, int l, int r, int aa, int bb) {
32     if(aa <= l && r <= bb) {
33         return mmax[x];
34     } else {
35         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
36         int ans = 0;
37         if(aa <= mid) ans = max(ans, query(ll, l, mid, aa, bb));
38         if(mid < bb) ans = max(ans, query(rr, mid + 1, r, aa, bb));
39         if(a[mid] < a[mid + 1]) ans = max(ans, min(rmax[ll], mid - aa + 1) + min(lmax[rr], bb - mid));
40         return ans;
41     }
42 }
43 
44 void build(int x, int l, int r) {
45     if(l == r) {
46         lmax[x] = rmax[x] = mmax[x] = 1;
47     } else {
48         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
49         build(ll, l, mid);
50         build(rr, mid + 1, r);
51         if(a[mid] < a[mid + 1]) {
52             lmax[x] = lmax[ll] + (lmax[ll] == mid - l + 1) * lmax[rr];
53             rmax[x] = rmax[rr] + (rmax[rr] == r - mid) * rmax[ll];
54             mmax[x] = max(rmax[ll] + lmax[rr], max(mmax[ll], mmax[rr]));
55         } else {
56             lmax[x] = lmax[ll];
57             rmax[x] = rmax[rr];
58             mmax[x] = max(mmax[ll], mmax[rr]);
59         }
60     }
61 }
62 
63 int main() {
64     scanf("%d", &T);
65     while(T--) {
66         scanf("%d%d", &n, &m);
67         for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
68         build(1, 0, n - 1);
69         while(m--) {
70             char c;
71             int a, b;
72             scanf(" %c%d%d", &c, &a, &b);
73             if(c == ‘Q‘) printf("%d\n", query(1, 0, n - 1, a, b));
74             else update(1, 0, n - 1, a, b);
75         }
76     }
77 }
View Code

 


联系
我们