首页 > 代码库 > HDU 4718 The LCIS on the Tree（树链剖分）

HDU 4718 The LCIS on the Tree（树链剖分）

2024-07-02 15:33:17   231人阅读

Problem Description
For a sequence S1, S2, ... , SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 < ... < Sj-1 < Sj , then the sequence Si, Si+1, ... , Sj is a CIS(Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).
Now we consider a tree rooted at node 1. Nodes have values. We have Q queries, each with two nodes u and v. You have to find the shortest path from u to v. And write down each nodes‘ value on the path, from u to v, inclusive. Then you will get a sequence, and please show us the length of its LCIS.
 
Input
The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 ... , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N - 1 numbers p2, p3, p4 ... , pN, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.
Then comes a number Q, it is the number of queries. (Q <= 105)
For next Q lines, each with two numbers u and v. As described above.
 
Output
For test case X, output "Case #X:" at the first line.
Then output Q lines, each with an answer to the query.
There should be a blank line *BETWEEN* each test case.
 
题目大意：给你一棵树，每个点上有一个权值，Q个询问，问u到v的最短路径上的点权都取出来排成一排，这一段的LCIS是多少（最长连续上升子序列）。
思路：还算是比较裸的树链剖分，每条链用一个线段树来维护，不过要同时维护太多的东西难度有点高……反正不会有修改操作，果断把从某个点开始的LCIS等等改成了预处理……反正就是相当的麻烦……手欠开了一条麻烦得要死的题目……
 
代码（2062MS）：
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int MAXV = 100010;
  8 const int MAXE = MAXV;
  9 const int MAXT = MAXV << 2;
 10 
 11 int lmaxi[MAXT], rmaxi[MAXT], mmaxi[MAXT];
 12 int lmaxd[MAXT], rmaxd[MAXT], mmaxd[MAXT];
 13 int val[MAXV], n, m, T;
 14 
 15 int inc_ord[MAXV], dec_ord[MAXV], inc_rev[MAXV], dec_rev[MAXV];
 16 
 17 void init_inc_dec() {
 18     for(int i = 1, t = 1; i <= n; ++i) {
 19         if(t < i) t = i;
 20         while(t < n && val[t] < val[t + 1]) ++t;
 21         inc_ord[i] = t - i + 1;
 22     }
 23     for(int i = 1, t = 1; i <= n; ++i) {
 24         if(t < i) t = i;
 25         while(t < n && val[t] > val[t + 1]) ++t;
 26         dec_ord[i] = t - i + 1;
 27     }
 28     for(int i = n, t = n; i > 0; --i) {
 29         if(t > i) t = i;
 30         while(t > 0 && val[t] < val[t - 1]) --t;
 31         inc_rev[i] = i - t + 1;
 32     }
 33     for(int i = n, t = n; i > 0; --i) {
 34         if(t > i) t = i;
 35         while(t > 0 && val[t] > val[t - 1]) --t;
 36         dec_rev[i] = i - t + 1;
 37     }
 38 }
 39 
 40 int queryI(int x, int l, int r, int a, int b) {
 41     if(a <= l && r <= b) {
 42         return mmaxi[x];
 43     } else {
 44         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
 45         int ans = 0;
 46         if(a <= mid) ans = max(ans, queryI(ll, l, mid, a, b));
 47         if(mid < b) ans = max(ans, queryI(rr, mid + 1, r, a, b));
 48         if(val[mid] < val[mid + 1]) {
 49             ans = max(ans, min(rmaxi[ll], mid - a + 1) + min(lmaxi[rr], b - mid));
 50         }
 51         return ans;
 52     }
 53 }
 54 
 55 int queryD(int x, int l, int r, int a, int b) {
 56     if(a <= l && r <= b) {
 57         return mmaxd[x];
 58     } else {
 59         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
 60         int ans = 0;
 61         if(a <= mid) ans = max(ans, queryD(ll, l, mid, a, b));
 62         if(mid < b) ans = max(ans, queryD(rr, mid + 1, r, a, b));
 63         if(val[mid] > val[mid + 1]) {
 64             ans = max(ans, min(rmaxd[ll], mid - a + 1) + min(lmaxd[rr], b - mid));
 65         }
 66         return ans;
 67     }
 68 }
 69 
 70 void maintainI(int x, int l, int r) {
 71     int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
 72     if(val[mid] < val[mid + 1]) {
 73         lmaxi[x] = lmaxi[ll] + (lmaxi[ll] == mid - l + 1) * lmaxi[rr];
 74         rmaxi[x] = rmaxi[rr] + (rmaxi[rr] == r - mid) * rmaxi[ll];
 75         mmaxi[x] = max(rmaxi[ll] + lmaxi[rr], max(mmaxi[ll], mmaxi[rr]));
 76     } else {
 77         lmaxi[x] = lmaxi[ll];
 78         rmaxi[x] = rmaxi[rr];
 79         mmaxi[x] = max(mmaxi[ll], mmaxi[rr]);
 80     }
 81 }
 82 
 83 void maintainD(int x, int l, int r) {
 84     int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
 85     if(val[mid] > val[mid + 1]) {
 86         lmaxd[x] = lmaxd[ll] + (lmaxd[ll] == mid - l + 1) * lmaxd[rr];
 87         rmaxd[x] = rmaxd[rr] + (rmaxd[rr] == r - mid) * rmaxd[ll];
 88         mmaxd[x] = max(rmaxd[ll] + lmaxd[rr], max(mmaxd[ll], mmaxd[rr]));
 89     } else {
 90         lmaxd[x] = lmaxd[ll];
 91         rmaxd[x] = rmaxd[rr];
 92         mmaxd[x] = max(mmaxd[ll], mmaxd[rr]);
 93     }
 94 }
 95 
 96 void build(int x, int l, int r) {
 97     if(l == r) {
 98         lmaxi[x] = rmaxi[x] = mmaxi[x] = 1;
 99         lmaxd[x] = rmaxd[x] = mmaxd[x] = 1;
100     } else {
101         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
102         build(ll, l, mid);
103         build(rr, mid + 1, r);
104         maintainI(x, l, r);
105         maintainD(x, l, r);
106     }
107 }
108 
109 int v[MAXV];
110 int fa[MAXV], son[MAXV], size[MAXV], tid[MAXV], top[MAXV], dep[MAXV];
111 int head[MAXV], ecnt, dfs_clock;
112 int to[MAXE], next[MAXE];
113 
114 void init(int n) {
115     memset(head, -1, (n + 1) * sizeof(int));
116     ecnt = dfs_clock = 0;
117 }
118 
119 void add_edge(int u, int v) {
120     to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;
121 }
122 
123 void dfs_size(int u, int depth) {
124     size[u] = 1; son[u] = 0; dep[u] = depth;
125     int maxsize = 0;
126     for(int p = head[u]; ~p; p = next[p]) {
127         int &v = to[p];
128         dfs_size(v, depth + 1);
129         size[u] += size[v];
130         if(size[v] > maxsize) {
131             son[u] = v;
132             maxsize = size[v];
133         }
134     }
135 }
136 
137 void dfs_heavy_edge(int u, int ancestor) {
138     val[tid[u] = ++dfs_clock] = v[u];
139     top[u] = ancestor;
140     if(son[u]) dfs_heavy_edge(son[u], ancestor);
141     for(int p = head[u]; ~p; p = next[p]) {
142         int &v = to[p];
143         if(v == son[u]) continue;
144         dfs_heavy_edge(v, v);
145     }
146 }
147 
148 int query(int x, int y) {
149     int res = 0, maxx = 0, prex = 0, maxy = 0, prey = 0;
150     while(top[x] != top[y]) {
151         if(dep[top[x]] > dep[top[y]]) {
152             int sz = dep[x] - dep[top[x]] + 1;
153             int up_ans = min(inc_rev[tid[x]], sz);
154             int down_ans = min(dec_ord[tid[top[x]]], sz);
155             res = max(res, queryD(1, 1, n, tid[top[x]], tid[x]));
156             if(prex && v[prex] >= v[x]) maxx = 0;
157             res = max(res, up_ans + maxx);
158             maxx = down_ans + (sz == down_ans) * maxx;
159             prex = top[x];
160             x = fa[top[x]];
161         } else {
162             int sz = dep[y] - dep[top[y]] + 1;
163             int up_ans = min(dec_rev[tid[y]], sz);
164             int down_ans = min(inc_ord[tid[top[y]]], sz);
165             res = max(res, queryI(1, 1, n, tid[top[y]], tid[y]));
166             if(prey && v[prey] <= v[y]) maxy = 0;
167             res = max(res, up_ans + maxy);
168             maxy = down_ans + (sz == down_ans) * maxy;
169             prey = top[y];
170             y = fa[top[y]];
171         }
172     }
173     if(dep[x] > dep[y]) {
174         int sz = dep[x] - dep[y] + 1;
175         int up_ans = min(inc_rev[tid[x]], sz);
176         int down_ans = min(dec_ord[tid[y]], sz);
177         res = max(res, queryD(1, 1, n, tid[y], tid[x]));
178         if(prex && v[prex] >= v[x]) maxx = 0;
179         if(prey && v[prey] <= v[y]) maxy = 0;
180         res = max(res, up_ans + maxx);
181         res = max(res, down_ans + maxy);
182         if(up_ans == sz) res = max(res, maxx + up_ans + maxy);
183     } else {
184         int sz = dep[y] - dep[x] + 1;
185         int up_ans = min(dec_rev[tid[y]], sz);
186         int down_ans = min(inc_ord[tid[x]], sz);
187         res = max(res, queryI(1, 1, n, tid[x], tid[y]));
188         if(prex && v[prex] >= v[x]) maxx = 0;
189         if(prey && v[prey] <= v[y]) maxy = 0;
190         res = max(res, down_ans + maxx);
191         res = max(res, up_ans + maxy);
192         if(up_ans == sz) res = max(res, maxx + up_ans + maxy);
193     }
194     return res;
195 }
196 
197 int main() {
198     scanf("%d", &T);
199     for(int t = 1; t <= T; ++t) {
200         scanf("%d", &n);
201         init(n);
202         for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
203         for(int i = 2; i <= n; ++i) {
204             scanf("%d", &fa[i]);
205             add_edge(fa[i], i);
206         }
207         dfs_size(1, 1);
208         dfs_heavy_edge(1, 1);
209         build(1, 1, n);
210         init_inc_dec();
211         printf("Case #%d:\n", t);
212         scanf("%d", &m);
213         while(m--) {
214             int u, v;
215             scanf("%d%d", &u, &v);
216             printf("%d\n", query(u, v));
217         }
218         if(t != T) puts("");
219     }
220 }
View Code

 


联系
我们