Prob1
(Analysis by Andi Qu)
Let's call two adjacent cows "linked" if they are able to pair up
with each other. We can split the cows up into chains where each pair of
adjacent cows in a chain are linked, and no two cows in different chains
are linked.
In each case below, we process each chain independently -- let
$n$ be the length of the current chain.
Case 1: $T = 1$
For chains with an even number of cows, we can pair up all of them. For
chains with an odd number of cows, we want to have exactly 1 unpaired
cow. If we leave more than 1 cow unpaired, then we can split the chain
into an odd-length suffix with 1 unpaired cow and an even-length prefix
with all the other unpaired cows. Since the prefix has an even length,
we can pair up all of its cows, which would result in a smaller sum of
weights of unpaired cows.
We can thus iterate through each cow in odd-length chains, check whether
it can be unpaired (removing it should not result in two odd-length
chains), and finally, leave the least valuable cow unpaired.
This case can thus be solved in $\mathcal O(N)$ time.
Case 2: $T = 2$
In this case, we should try to leave unpaired cows in both even- and
odd-length chains. We can use dynamic programming to solve this in
$\mathcal O(N \log N)$ time.
Let $\texttt{dp}[i][j]$ be the maximum sum of values of
unpaired cows if we only consider $i$ to $n$ cows
in the current chain and there are $j$ unpaired ones. Let
$\texttt{ub}[i]$ be the index of the leftmost cow to the
right of cow $i$ that can be unpaired if cow $i$
is unpaired (or $n + 1$ if it doesn't exist). We can compute
$\texttt{ub}[i]$ using binary search.
If it's possible to leave cow $i$ unpaired with
$j$ unpaired cows, then $\texttt{dp}[i][j] =
\max(\texttt{dp}[i + 1][j], \texttt{dp}[\texttt{ub}[i]][j -
1] + y_i)$. Otherwise, $\texttt{dp}[i][j] =
\texttt{dp}[i + 1][j]$.
Since we only care about the parity of the number of unpaired cows, we
can drop the second dimension of the DP array. This allows us to compute
the whole DP array in $\mathcal O(N \log N)$ time (which
can easily be reduced to $\mathcal O(N)$).
让我们称相邻的两头奶牛为“相关的”，如果它们能够配对。我们可以将奶牛分成链，其中每一对相邻的奶牛都是相关的，不同链中的任意两头奶牛都不相关。
在下面的每种情况中，我们独立地处理每个链 - 让$n$成为当前链的长度。
情况1：$T = 1$
对于有偶数头奶牛的链，我们可以将它们全部配对。对于有奇数头奶牛的链，我们希望恰好有1头未成对的奶牛。如果我们留下超过1头未成对的奶牛，则可以将该链拆分成一个长度为奇数的后缀，其中只有1头未成对的奶牛和一个长度为偶数的前缀，其中所有其他未成对的奶牛都在。由于前缀的长度是偶数，我们可以将它的所有奶牛配对，这将导致未成对奶牛的重量之和更小。
因此，我们可以迭代地遍历奇数长度的链中的每头奶牛，检查它是否可以独自一对（将它从链中移除不应该导致两个奇数长度的链），最后将最不有价值的奶牛单独一对。
这个情况可以在$\mathcal O(N)$的时间内解决。
情况2：$T=2$
在这种情况下，我们应尽量让偶数和奇数长度的链中都留下未成对的奶牛。我们可以使用动态规划在$\mathcal{O(N\log N)}$的时间内解决此问题。
让$\texttt{dp}[i][j]$表示如下条件下，考虑链中$i$到$n$奶牛，其中有$j$头未成对的奶牛时可以获得的最大未成对奶牛价值总和。让$\texttt{ub}[i]$表示：当第$i$头奶牛未成对时，它右侧最左边的奶牛的索引，该奶牛也能够单独一对（如果不存在这样的牛，则设为$n+1$）。我们可以使用二分查找计算$\texttt{ub}[i]$。
如果可以留下第$i$头奶牛未成对且有$j$头未成对的奶牛，则$\texttt{dp}[i][j] = \max (\texttt{dp}[i+1][j], \texttt{dp}[\texttt{ub}[i]][j-1] + y_i)$。否则，$\texttt{dp}[i][j] = \texttt{dp}[i+1][j]$。
由于我们只关心未成对的奶牛数量的奇偶性，因此可以省略DP数组的第二个维度。这使得我们可以在$\mathcal{O(N\log N)}$的时间内计算整个DP数组（通常还可以简化为$\mathcal{O(N)}$）。
Andi's code:
#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
const int INF = 1e9;
int min_span_cost(vector<pair<int, int>>& span, int k) {
int mn = INF;
for (int i = 0; i < span.size(); i++) {
if (!(i & 1) || span[i + 1].first - span[i - 1].first <= k)
mn = min(mn, span[i].second);
}
return mn;
}
int max_span_cost(vector<pair<int, int>>& span, int k) {
int n = span.size();
if (!n) return 0;
vector<pair<int, int>> dp(n + 1);
dp[n] = {0, -INF};
for (int i = n - 1; ~i; i--) {
dp[i] = dp[i + 1];
int ub = upper_bound(span.begin(), span.end(),
make_pair(span[i].first + k, INF)) -
span.begin();
if (i == 0 || i == n - 1 ||
span[i + 1].first - span[i - 1].first <= k || !(n - i & 1))
dp[i].first = max(dp[i].first, dp[ub].second + span[i].second);
if (i == 0 || i == n - 1 ||
span[i + 1].first - span[i - 1].first <= k || (n - i & 1))
dp[i].second = max(dp[i].second, dp[ub].first + span[i].second);
}
return (n & 1 ? dp[0].second : dp[0].first);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t, n, k;
cin >> t >> n >> k;
int prev_x = 0, ans = 0;
vector<pair<int, int>> curr_span;
while (n--) {
int x, y;
cin >> x >> y;
if (x - prev_x > k) {
if (t == 1) {
if (curr_span.size() & 1) ans += min_span_cost(curr_span, k);
} else
ans += max_span_cost(curr_span, k);
curr_span.clear();
}
curr_span.push_back({x, y});
prev_x = x;
}
if (t == 1) {
if (curr_span.size() & 1) ans += min_span_cost(curr_span, k);
} else
ans += max_span_cost(curr_span, k);
cout << ans;
return 0;
}
Prob2
(Analysis by Andi Qu, Benjamin Qi)
To solve this problem in $\mathcal O(N^2)$ time, we can
simulate the process for each $x$.
为了在$\mathcal O(N^2)$时间内解决这个问题，我们可以模拟每个$x$的过程。
#include <iostream>
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n, p[200001];
std::cin >> n;
for (int i = 0; i < n; i++) std::cin >> p[i];
for (int x = 0; x <= n; x++) {
int mn = 0, mx = n + 1, ans = 0;
bool hi = false;
for (int i = 0; i < n; i++) {
if (p[i] > mx || p[i] < mn) continue;
if (p[i] > x) {
hi = true;
mx = p[i];
} else {
ans += hi;
hi = false;
mn = p[i];
}
}
std::cout << ans << 'n';
}
return 0;
}
Another solution that takes $\mathcal O(N^2)$ time in the
worst case is to keep track of each "HI" and "LO" for each
$x$, and then go through the 2 lists to find the number of
"HILO" pairs. However, this solution passes the test cases with data
generated uniformly at random because the expected number of "HI"s and
"LO"s is $\mathcal{O}(\log N)$ for each $x$,
resulting in an overall expected runtime of $\mathcal{O}(N\log
N)$.
To keep track of the 2 lists, we can use 2 monotone
stacks. Essentially, we maintain a
sorted list of indices where Bessie says "LO". When we transition from
$x$ to $x + 1$, we know that the last "LO" that
Bessie will say will be to $x + 1$. If Bessie doesn't say
"LO" to $k$ while thinking of $x + 1$, then she
will never say "LO" to some $k$ while thinking of $y >
x + 1$, so we can remove all "LO"s that used to be said after
the index of $x + 1$ in the permutation.
Conveniently, the indices that we remove form a suffix of the list
(because the list is sorted), so we can use a stack and pop elements
from it. Since each index is pushed into and popped from the stack at
most once, this takes $\mathcal O(N)$ time overall;
iterating through the stack for each $x$ takes a further
$\mathcal O(N)$ time per element.
Here's a C++ code snippet for finding the list of "LO"s for each
$x$:
另一种在最坏情况下需要 $\mathcal O(N^2)$ 时间的解决方案是对每个$x$跟踪其每个“HI”和“LO”，然后遍历这两个列表以找到“HILO”对的数量。但是，由于每个$x$的“HI”和“LO”的期望数量是 $\mathcal{O}(\log N)$ ，因此这个解决方案在随机生成的数据测试用例中可以通过，从而导致总体期望运行时间为 $\mathcal{O}(N\log N)$。
为了跟踪这两个列表，我们可以使用 2 个 单调栈。本质上，我们维护了一个 Bessie 说“LO”的索引的排序列表。当我们从$x$转移到$x+1$时，我们知道 Bessie 最后一个“LO”是在$x+1$处说的。如果 Bessie 没有在思考$x+1$时说“LO”到$k$，那么她将永远不会在思考 $y > x + 1$ 时说“LO”到某些 $k$，因此我们可以从排列中删除在 $x+1$ 索引之后曾经说过“LO”的所有元素。
方便的是，我们需要删除的索引构成列表的后缀（因为列表是排序的），因此我们可以使用栈和弹出元素。由于每个索引最多只被推入和弹出一次，因此总共需要 $\mathcal O(N)$ 的时间；对于每个$x$迭代栈需要额外 $\mathcal O(N)$ 的时间。
以下是查找每个$x$的“LO”列表的 C++ 代码片段：
std::vector<int> los[200001];
for (int i = 1; i <= n; i++) {
los[i] = los[i - 1];
while (los[i].size() != 0 && los[i].back() > pos[i]) los[i].pop_back();
los[i].push_back(pos[i]);
}
(Bonus: Find out how the rest of the test data for this problem was
generated.)
To solve the problem in $\mathcal O(N)$ time, we need a way
to efficiently transition from $x$ to $x + 1$.
Full Solution 1:
Claim: Let $p$ be the given permutation. If index
$i$ is the "LO" in a "HILO" pair, then the "HI" in the
pair must be the index $k$ such that $k < i$,
$p[k] > p[i]$, and $p[k]$ is minimal.
Proof: If no such $k$ exists, then there is no greater
element before $i$, so $i$ can't be the "LO" in
a "HILO" pair. If Bessie says "LO" to $p[k]$, then
Elsie will not guess $p[i]$, so $i$ can't be
the "LO" in a "HILO" pair. Otherwise, the last "HI" that Bessie
says, before saying "LO" to $p[i]$, must be to
$p[k]$.
Knowing this, we can compute an array $\texttt{prv}$ where
$\texttt{prv}[i] = k$ as described above using a monotone
stack.
Claim: Let index $j$ be the last "LO" before Bessie
says "LO" to $p[i]$. For each $x$ where Elsie
doesn't skip $p[i]$, $j$ is the same.
Proof: Let $j_1 < j_2 < i$ and $p[j_1], p[j_2] <
p[i]$. If Bessie says "LO" to $p[i]$, then
there are 3 possibilities:
- Bessie never says "LO" to either $p[j_1]$ or
$p[j_2]$ because she already said "LO" at some index
$k < j_1$ where $p[k] > p[j_1],
p[j_2]$.
- Bessie always says "LO" to $p[j_1]$ but never to
$p[j_2]$ because she said "LO" at some index $j_1
\leq k < j_2$ where $p[k] > p[j_2]$.
- Bessie always "LO" to both $p[j_1]$ and
$p[j_2]$ because neither of the above happen.
If transitioning causes Bessie to stop saying "LO" to some index
before $i$, then it must also cause her to stop saying "LO"
to $p[i]$ too. Therefore, $j$ is the same for
each $p[i]$.
Claim: Let $j$ be defined as above. Index $i$
is the "LO" in a "HILO" pair if and only
$\texttt{prv}[i]$ exists, and $j$ doesn't
exist or $\texttt{prv}[i] \neq \texttt{prv}[j]$.
Proof: If $\texttt{prv}[i]$ doesn't exist, then
Bessie never says "HI" before saying "LO" to $p[i]$, so
it can't be the "LO" in a "HILO" pair. Otherwise, if
$\texttt{prv}[i] \neq \texttt{prv}[j]$, then the last
"HI" that Bessie says before saying "LO" to $p[i]$ must
be after saying "LO" to $p[j]$ by definition. In this
case, index $i$ is the "LO" in a "HILO" pair.
Knowing this, we can then determine, once for each index, whether it's
the "LO" in a "HILO" pair, and thus how many "HILO" pairs there
are for each $x$.
为了在 $\mathcal O(N)$ 时间内解决这个问题，我们需要一种有效地从 $x$ 过渡到 $x+1$ 的方法。
全面解决方案 1：
声明： 令 $p$ 为给定的排列。如果索引 $i$ 是“HILO”对中的“LO”，则该对中的“HI”必须是索引 $k$，满足 $k < i$，$p[k] > p[i]$，且 $p[k]$ 是最小的。
证明： 如果不存在这样的 $k$，则在 $i$ 之前没有更大的元素，因此 $i$ 不能是“HILO”对中的“LO”。如果 Bessie对 $p[k]$ 说“LO”，则Elsie不会猜测 $p[i]$，因此 $i$ 不能是“HILO”对中的“LO”。否则，在Bessie最后一次说“LO”之前，她所说的最后一个“HI”必须是对 $p[k]$。
了解这些，我们可以使用单调栈计算一个数组 $\texttt{prv}$，其中 $\texttt{prv}[i]=k$，其中 $k$ 如上所述,以有效地从 $x$ 过渡到 $x+1$。
声明： 索引 $j$ 是 Bessie 在对 $p[i]$ 说“LO”之前的最后一个“LO”。对于 Elsie 不跳过 $p[i]$ 的每个 $x$，$j$ 都是相同的。
证明： 令 $j_1 < j_2 < i$，且 $p[j_1],p[j_2] < p[i]$。如果 Bessie 对 $p[i]$ 说“LO”，则有三种可能：
Bessie从未对$p[j_1]$或$p[j_2]$说“LO”，因为她已经在一些索引$k< j_1$处说过“LO”，且$p[k]>p[j_1],p[j_2]$。
Bessie总是对$p[j_1]$说“LO”，但不对$p[j_2]$说，因为她在某个索引$j_1\leq k < j_2$处说过“LO”，且$p[k]>p[j_2]$。
Bessie总是同时对$p[j_1]$和$p[j_2]$说“LO”，因为以上两种情况都未发生。
如果从$x$过渡导致Bessie在$i$之前停止对某个索引说“LO”，则它也必须导致她停止对$p[i]$说“LO”。因此，$j$对于每个$p[i]$是相同的。
声明： 如上所述定义$j$。若存在$\texttt{prv}[i]$且$j$不存在或$\texttt{prv}[i]\neq\texttt{prv}[j]$，则索引$i$是“HILO”对中的“LO”。
证明： 如果$\texttt{prv}[i]$不存在，则Bessie在对$p[i]$说“LO”之前从未说过“HI”，因此它不能是“HILO”对中的“LO”。否则，如果$\texttt{prv}[i]\neq\texttt{prv}[j]$，则Bessie在对$p[i]$说“LO”之前最后说的“HI”一定是在按定义对$p[j]$说“LO”之后。在这种情况下，索引$i$是“HILO”对中的“LO”。
知道了这些，我们可以对于每个索引确定它是否是“HILO”对中的“LO”，从而确定每个$x$中有多少“HILO”对。
Andi's code:
#include <iostream>
#include <stack>
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n, pos[200001], prv[200001];
bool hilo[200001];
std::cin >> n;
for (int i = 1; i <= n; i++) {
int p;
std::cin >> p;
pos[p] = i;
}
std::stack<int> stck;
stck.push(0);
for (int i = n; i > 0; i--) {
while (stck.top() > pos[i]) stck.pop();
prv[pos[i]] = stck.top();
stck.push(pos[i]);
}
while (stck.size() != 1) stck.pop();
std::cout << "0n";
int cnt = 0;
for (int i = 1; i <= n; i++) {
while (stck.top() > pos[i]) {
cnt -= hilo[stck.top()];
stck.pop();
}
hilo[pos[i]] = prv[pos[i]] != 0 &&
(stck.top() == 0 || prv[pos[i]] != prv[stck.top()]);
stck.push(pos[i]);
cnt += hilo[pos[i]];
std::cout << cnt << 'n';
}
return 0;
}
Full Solution 2: Another way we can solve this problem in
$\mathcal O(N \log N)$ time is with stacks plus a sorted
set.
First, we compute, for each $x \rightarrow x + 1$ event,
which elements of the permutation start and stop becoming "HI"s and
"LO"s. We can do this with a stack.
Next, we process the events for each $x$. We can maintain an
ordered map of "HI"s and "LO"s, and inserting or erasing any element
from that map changes a constant number of "HILO" pairs. Using C++'s
iterators, we can process these changes efficiently.
完整解答 2： 另一种我们可以在$\mathcal O(N \log N)$时间内解决这个问题的方式是使用堆栈加上一个排序的集合。
首先，我们对于每个$x \rightarrow x + 1$事件，计算开始和停止成为“HI”和“LO”的置换元素。我们可以使用一个堆栈来完成这个任务。
接下来，我们处理每个$x$的事件。我们可以维护一个有序映射，包含“HI”和“LO”。插入或删除该映射中的任何元素会改变一定数量的“HILO”对。使用C++的迭代器，可以有效地处理这些更改。
Ben's code:
#include <bits/stdc++.h>
using namespace std;
template <class T> using V = vector<T>;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
V<int> P(N);
for (auto &t : P) {
cin >> t;
--t;
}
V<int> pos(N);
for (int i = 0; i < N; ++i)
pos[P[i]] = i;
V<V<pair<int, char>>> to_ins(N + 1);
V<V<int>> to_del(N + 1);
{ // process "LO"s from lowest to highest, record insertions and deletions
stack<int> cur;
for (int i = 0; i < N; ++i) {
while (!cur.empty() && cur.top() > pos[i]) {
to_del.at(i + 1).push_back(cur.top());
cur.pop();
}
cur.push(pos[i]);
to_ins.at(i + 1).push_back({pos[i], 'L'});
}
}
{ // process "HI"s from highest to lowest, record insertions and deletions
stack<int> cur;
for (int i = N - 1; i >= 0; --i) {
while (!cur.empty() && cur.top() > pos[i]) {
to_ins.at(i + 1).push_back({cur.top(), 'H'});
cur.pop();
}
cur.push(pos[i]);
to_del.at(i + 1).push_back(pos[i]);
}
while (!cur.empty()) {
to_ins.at(0).push_back({cur.top(), 'H'});
cur.pop();
}
}
int ans = 0;
map<int, char> m; // maps each position to 'H' or 'L'
auto hilo = [&](map<int, char>::iterator it,
map<int, char>::iterator next_it) {
return it->second == 'H' && next_it->second == 'L';
};
auto get_dif = [&](map<int, char>::iterator it) {
int dif = 0;
if (it != begin(m))
dif += hilo(prev(it), it);
if (next(it) != end(m))
dif += hilo(it, next(it));
if (it != begin(m) && next(it) != end(m))
dif -= hilo(prev(it), next(it));
return dif;
};
for (int i = 0; i <= N; ++i) { // to finish, go from lowest to highest again
for (auto &t : to_del.at(i)) {
auto it = m.find(t);
assert(it != end(m));
ans -= get_dif(it);
m.erase(it);
}
for (auto &t : to_ins.at(i)) {
auto it = m.insert(t).first;
assert(it->second);
ans += get_dif(it);
}
cout << ans << "n";
}
}
Full Solution 3: Here is a simpler solution that also runs in
$\mathcal O(N\log N)$. This one doesn't explicitly make
use of monotonic stacks, though it is possible to modify it to run in
$\mathcal O(N)$ time with them.
完整解答 3： 这是一种更简单的解决方案，也可以在$\mathcal O(N\log N)$时间内运行。这种方法没有明确地使用单调栈，但是可以通过修改它们来使其在$\mathcal O(N)$时间内运行。
首先，我们使用一个数组$tot$来记录$h_1, h_2, \ldots, h_n$中每个元素的前缀和。我们还用一个$set$来存储之前遇到的每个$h_i$值，以便我们可以轻松查找比当前$h_i$值小的元素数量和比当前$h_i$值大的元素的数量。这可以使用$set$的$lower\_bound$函数进行。
我们现在可以遍历$h$数组，对于每个$h_i$值，我们可以计算小于$h_i$的值的数量和大于$h_i$的值的数量。这些数量可以通过查询set中的两个边界得到。我们可以将这些数量相乘，加入到答案中。然后将$h_i$插入到$set$中。
时间复杂度为$\mathcal O(N\log N)$，由于我们需要用$set$来存储过去的$h_i$值。如果我们将该set替换为单调栈，可以在$\mathcal O(N)$时间内求解该问题。
Allen Wu's code:
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i)
cin >> arr[i];
vector<int> pos(n + 1);
for (int i = 0; i < n; ++i)
pos[arr[i]] = i;
map<int, int> existing;
vector<int> changes(n + 1);
for (int i = 0; i < n; ++i) {
int num = arr[i];
// goal is to compute how the number of HILOs changes
// when we go from x = num-1 to x = num
auto it = existing.upper_bound(num);
if (it != existing.end()) {
// add one if num is involved in a HILO when x = num
if (it == existing.begin())
++changes[num];
else if (it->second > prev(it)->second)
++changes[num];
}
// subtract one if num is involved in a HILO when x = num-1
if (pos[num - 1] > pos[num])
--changes[num];
existing[num] = i;
}
int sum = 0;
for (int i = 0; i <= n; ++i) {
sum += changes[i];
cout << sum << "n";
}
}
Prob3
(Analysis by Andi Qu)
For each sub-case, we need to check 4 conditions:
Condition 1: Every color appears in a contiguous range of
$x$'s.
We can check this condition by maintaining an array that describes at
which $x$ a color last appeared. If the last $x$
is always 1 less than the current $x$, then this condition
holds.
Sub-case 2 in the example does not satisfy this condition.
Condition 2: For each $x$, if one appearance of color
$a$ is after the first appearance and before the second
appearance of color $b$, then the other appearance of color
$a$ must do the same.
Let's say that a color becomes "activated" when it appears for the
first time, and then "deactivated" when it appears the second time. We
can then check this condition by maintaining a stack of active colors.
When a color becomes deactivated, it must be at the top of the stack. If
this is always true, then this condition holds.
Sub-case 3 in the example does not satisfy this condition.
If the 2 appearances of color $a$ are between the 2
appearances of color $b$, then we know that bracelet
$a$ must be contained inside bracelet $b$. This
hierarchical relationship allows us to transform the bracelets into a
tree structure, where:
- The nodes are the bracelets.
- If a bracelet is contained by another bracelet, then its parent is
the innermost bracelet that contains it.
- Otherwise, its parent is a placeholder node (e.g. node
$0$).
Condition 3: Each node's parent in the tree must be consistent for
every $x$ it appears in.
This is because if some color appears, then its parent must also appear.
We can check this condition by maintaining an array describing the
parents of colors we've seen before. We can then check this array
against the input for each $x$.
Condition 4: The ordering of colors in the input must be consistent
for every $x$ it appears in.
We can check this condition by maintaining 2 lists -- one for the
current $x$'s color order and the other for all previous
$x$'s' color order. To check the ordering, we can compare
the ordering of these two lists' intersection, and then merge the lists
after processing $x$ by using 2 pointers. Since the
constraints are so small, straightforward list insertion is fast enough
for this.
Sub-case 5 in the example does not satisfy this condition.
Andi's code (which runs in $\mathcal{O}(N^2M)$ time).
对于每个子问题，我们需要检查四个条件：
条件1： 每种颜色都出现在$x$的一个连续范围内。
我们可以通过维护一个数组来检查此条件，该数组描述每种颜色上次出现在哪个$x$。如果最后一个$x$始终比当前$x$小1，则符合此条件。
例如，示例中的子问题2不满足此条件。
条件2：对于每个$x$ ，如果颜色$a$的一个出现在颜色$b$的第一次出现之后且第二次出现之前，则颜色$a$的另一个出现也必须满足同样的条件。
我们可以使用“活动”颜色的堆栈来检查此条件。颜色第一次出现时，它被激活，当它第二次出现时被“取消激活”。然后，当一个颜色被“取消激活”时，它必须在堆栈的顶部。如果始终如此，则符合此条件。
示例中的子问题3不满足此条件。
如果颜色$a$的两次出现都在颜色$b$的两次出现之间，则我们知道手镯$a$必须包含在手镯$b$中。这种层次关系允许我们将手镯转换为树结构，其中：
- 节点是手镯。
- 如果一个手镯被另一个手镯包含，则其父节点是包含它的最内层手镯。
- 否则，其父节点是一个占位符节点（例如节点0）。
条件3： 树中每个节点的父节点必须在它出现的每个$x$中保持一致。
这是因为如果某种颜色出现，则其父节点也必须出现。我们可以通过维护一个描述之前看到的颜色的父节点的数组来检查此条件。然后，我们可以将此数组与每个$x$的输入进行比较，以检查该条件是否成立。
条件4： 输入中颜色的顺序必须在其出现的每个$x$中保持一致。
我们可以通过维护两个列表来检查此条件——一个用于当前$x$的颜色顺序，另一个用于所有之前$x$的颜色顺序。为了检查顺序，我们可以比较这两个列表的交集的顺序，并使用两个指针在处理完$x$后合并列表。由于约束非常小，直接列表插入对于这个问题来说已经足够快了。
示例中的子问题5不满足此条件。
Andi的代码的时间复杂度为$\mathcal{O}(N^2M)$。
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t, last_appeared[51], parent[51];
cin >> t;
while (t--) {
int n, m;
bool good = true;
vector<int> glob_order;
cin >> n >> m;
for (int i = 0; i <= n; i++) last_appeared[i] = parent[i] = -1;
while (m--) {
int k, curr = 0;
cin >> k;
stack<int> stck;
vector<int> curr_order;
while (k--) {
int c;
cin >> c;
if (!good) continue;
if (last_appeared[c] == m && stck.top() == c) {
stck.pop();
curr = parent[curr];
} else {
if ((~last_appeared[c] && last_appeared[c] != m + 1) ||
last_appeared[c] == m ||
(~last_appeared[c] && parent[c] != curr)) {
// Conditions 1, 2, and 3
good = false;
continue;
}
// Condition 4 part A
curr_order.push_back(c);
parent[c] = curr;
last_appeared[c] = m;
stck.push(c);
curr = c;
}
}
// Condition 4 part B
if (!good) continue;
int ptr = 0;
for (int i : curr_order) {
while (ptr != glob_order.size() &&
!count(curr_order.begin(), curr_order.end(), glob_order[ptr]))
ptr++;
if (!count(glob_order.begin(), glob_order.end(), i))
glob_order.insert(glob_order.begin() + ptr, i);
else if (ptr == glob_order.size() || glob_order[ptr] != i) {
good = false;
break;
}
ptr++;
}
}
cout << (good ? "YESn" : "NOn");
}
return 0;
}
Of course, it is possible to solve this problem in
$\mathcal{O}(NM)$ time, but it was not necessary to do so
due to the low constraints.
当然，可以在$\mathcal{O}(NM)$的时间复杂度内解决这个问题，但是由于约束条件较低，没有必要这样做。
