#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;
}
