P11665 [JOI 2025 Final] Just Long Neckties 2

因为限制带等于号，所以每个数在当前的序列只会出现一次。设 $f_S$ 表示当序列的数的集合是 $S$ 的时候最远能够到哪个位置。这样设计出来的状态的性质不太好，因为它没有什么单调性。不过考虑到任意增加序列的数只会让情况不优，所以完全可以对 $S$ 做 “高维前缀 $\max$”（这里并非真正的高维前缀 $\max$，仅供理解）：如果 $S$ 被 $T$ 偏序（$S$ 的第 $i$ 高位的 $1$ 不大于 $T$）且 $f_S > f_T$，那么用 $f_S$ 更新 $f_T$ 不会把答案算小。

更新即求出 $f_S$ 之后的第一对相邻的位置使得这两个位置的数都不在 $S$ 里，可以枚举这两个数是什么，但朴素做法的空间是 $\mathcal{O}(na ^ 2)$。对空间的优化是注意到这个巨大的数组里很多数都是相同的，我们考虑记录 $nxt_{i, v}$ 表示从 $i + 1$ 开始下一次 $a_i$ 和 $v$ 相邻出现是在什么位置，这样枚举第一个数的时候找到这个数在 $f_S$ 之后的第一次出现，再根据出现的位置和枚举的第二个数根据 $nxt$ 查表即可。这样的时间复杂度是 $\mathcal{O}(na + 2 ^ aa ^ 2)$。

不过笔者笨笨的，没有想到以上优化，所以他采用了另一种方法，时间和空间都略好一些。如果能按照 $f_S$ 从小到大的顺序枚举 $S$，那么只需支持 $nxt_{u, v}$ 上的撤销操作。类似拓扑排序的思想，只有当一个状态所有偏序的状态都转移了之后，才能转移它。但是一个状态可以偏序很多状态，不能把所有边都连上，怎么办呢？因为 $\max$ 的转移是可以重复的，所以不需要担心重复计算的问题，于是一个状态 $S$ 的所有偏序的状态可以由把它的每个 $1$ 向后移动一位（若下一位不是 $1$）得到的状态 $T_i$ 的所有偏序的状态（包括 $T_i$ 本身）的并得到。特别地，如果最低位是 $1$，那么相当于把这个 $1$ 给去掉。例如 $S = 101101$ 的 $T_i$ 分别是 $011101$，$101011$ 和 $101100$。还有一个问题是根据 $T$ 算它向哪些 $S$ 连边了，这个也很简单，就是把每个 $1$ 向前移动一位（若上一位不是 $1$），以及还有一种情况是如果最低位是 $0$ 那么把它变成 $1$。时间复杂度 $\mathcal{O}(n + 2 ^ aa ^ 2)$，空间 $\mathcal{O}(n + 2 ^ a)$。

此外，关于 TianTian2008 的 这篇题解，其复杂度并非线性，但是在现有数据规模下较难卡掉。构造 $6, 4, 5, 3, 2, 1$ 可以得到 $6, 4, 3, 1$ 和 $6, 5, 2, 1$ 两个相互不偏序的状态，将这样的构造叠加起来可以得到 $2 ^ {a / 5}$ 个相互不偏序的状态，所以时间复杂度为 $\Omega(2 ^ a + 2 ^ {a / 5}n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using LL = __uint128_t;
mt19937 rnd(1064);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}
bool Mbe;

constexpr int N = 5e6 + 5;
constexpr int M = 1 << 21;
int n, ans, a[N], f[M], g[M];
int mp[21][21], val[N];
vector<int> buc[N];

bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n, ans = 21;
  for(int i = 1; i <= n; i++) cin >> a[i], a[i]--;
  for(int i = 1; i < 1 << 21; i++) {
    for(int j = 0; j < 21; j++) {
      if(i >> j & 1) {
        g[i] += (j == 0) || (i >> (j - 1) & 1 ^ 1);
      }
    }
  }
  for(int i = 0; i < 21; i++) {
    for(int j = 0; j < 21; j++) {
      mp[i][j] = n + 1;
    }
  }
  for(int i = n - 1; i; i--) {
    int u = a[i], v = a[i + 1];
    if(u > v) swap(u, v);
    val[i] = mp[u][v], mp[u][v] = i;
  }
  buc[0].push_back(0);
  for(int _ = 0; _ <= n; _++) {
    if(_) {
      int u = a[_], v = a[_ + 1];
      if(u > v) swap(u, v);
      mp[u][v] = val[_];
    }
    while(!buc[_].empty()) {
      int S = buc[_].back();
      buc[_].pop_back();
      static int p[21], bit[21], ppc;
      for(int i = ppc = 0; i < 21; i++) {
        bit[i] = S >> i & 1;
        if(S >> i & 1) {
          p[ppc++] = i;
        }
      }
      if(ppc >= ans) continue;
      int nxt = n + 1;
      for(int i = 0; i < 21; i++) {
        if(bit[i]) continue;
        for(int j = i; j < 21; j++) {
          if(bit[j]) continue;
          nxt = min(nxt, mp[i][j]);
        }
      }
      if(nxt == n + 1) {
        ans = min(ans, ppc);
        continue;
      }
      int u = a[nxt], v = a[nxt + 1];
      auto trans1 = [&](int pos, int val) {
        int T;
        if(ppc == 0 || pos < p[0]) {
          T = S ^ (1 << pos);
        }
        for(int i = 0; i < ppc; i++) {
          if(i == ppc - 1 || pos < p[i + 1]) {
            T = S ^ (1 << p[i]) ^ (1 << pos);
            break;
          }
        }
        f[T] = max(f[T], val);
      };
      trans1(u, nxt);
      trans1(v, nxt + 1);

      auto trans2 = [&](int T) {
        f[T] = max(f[T], f[S]);
        if(!--g[T]) buc[f[T]].push_back(T);
      };
      for(int i = 0; i < ppc; i++) {
        if(i == ppc - 1) {
          if(p[i] != 20) {
            trans2(S ^ (1 << p[i]) ^ (1 << p[i] + 1));
          }
        }
        else if(p[i] + 1 < p[i + 1]) {
          trans2(S ^ (1 << p[i]) ^ (1 << p[i] + 1));
        }
      }
      if(ppc == 0 || p[0] != 0) {
        trans2(S ^ 1);
      }
    }
  }
  cout << ans << "\n";
  fprintf(stderr, "%.3lf\n", 1.0 * clock() / CLOCKS_PER_SEC);
  return 0;
}