#include <vector> #include <unordered_map> #include <utility> #include <algorithm> using std::vector; using std::unordered_map; using std::pair; class SegmentTree { public: SegmentTree(int size) : n(size) { tree.assign(4 * n, {0, -1}); } void update(int pos, int val) { update_tree(0, 0, n - 1, pos, val); } // query range [l, r] pair<int, int> query(int l, int r) { if (l > r) return {0, -1}; return query_tree(0, 0, n - 1, l, r); } private: int n; vector<pair<int, int>> tree; // {value, index} void update_tree(int node, int start, int end, int pos, int val) { if (start == end) { tree[node] = {val, pos}; return; } int mid = (start + end) / 2; if (pos <= mid) { update_tree(2 * node + 1, start, mid, pos, val); } else { update_tree(2 * node + 2, mid + 1, end, pos, val); } auto left = tree[2 * node + 1]; auto right = tree[2 * node + 2]; if (left.first > right.first) { tree[node] = left; } else if (right.first > left.first) { tree[node] = right; } else { // tie-breaker: prefer larger index if (left.second >= right.second) tree[node] = left; else tree[node] = right; } } pair<int, int> query_tree(int node, int start, int end, int l, int r) { if (r < start || end < l) { return {0, -1}; } if (l <= start && end <= r) { return tree[node]; } int mid = (start + end) / 2; pair<int, int> left_res = {0, -1}; pair<int, int> right_res = {0, -1}; if (l <= mid) { left_res = query_tree(2 * node + 1, start, mid, l, r); } if (r > mid) { right_res = query_tree(2 * node + 2, mid + 1, end, l, r); } if (left_res.first > right_res.first) { return left_res; } else if (right_res.first > left_res.first) { return right_res; } else { // tie-breaker: prefer larger index if (left_res.second >= right_res.second) return left_res; else return right_res; } } }; vector<int> ucs(vector<int> A, vector<int> B) { int n = (int)A.size(); int m = (int)B.size(); if (m == 0) return {}; // Build nextB: value -> list of indices in B unordered_map<int, vector<int>> nextB; for (int idx = 0; idx < m; ++idx) { int val = B[idx]; nextB[val].push_back(idx); } vector<int> f(m + 1, 0); vector<int> prev(m + 1, -1); int size = m; SegmentTree seg(size); for (int i = 0; i < n; ++i) { int a = A[i]; auto it = nextB.find(a); if (it == nextB.end()) continue; // Important: to match Python behavior, we must process indices of B in // ascending order, but since we’re using dp with segment tree and // referring only to prefix [0..j-1], this is fine. const vector<int>& indices = it->second; for (int j : indices) { int M, k; if (j > 0) { auto res = seg.query(0, j - 1); M = res.first; k = res.second; } else { M = 0; k = -1; } int candidate = M + 1; if (candidate > f[j]) { f[j] = candidate; prev[j] = k; seg.update(j, candidate); } } } int L = 0; int j0 = -1; for (int j = 0; j < m; ++j) { if (f[j] > L) { L = f[j]; j0 = j; } } if (L == 0) return {}; vector<int> U; int j = j0; int current_length = L; while (current_length > 0) { U.push_back(B[j]); j = prev[j]; current_length--; } std::reverse(U.begin(), U.end()); return U; }