自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:49:10，当前版本为作者最后更新于2023-09-17 14:46:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9522 [JOISC2022] 错误拼写

考虑 $T_{i}\leq T_{j}$ 的等价条件。模拟字典序比较的过程：

• 若 $i < j$，那么要么 $s_{i\sim j}$ 全部相等，要么 $s_i > s_p$，其中 $p$ 是从 $i$ 开始第一个不等于 $s_i$ 的位置。
• 若 $i > j$，那么要么 $s_{j\sim i}$ 全部相等，要么 $s_j < s_p$，其中 $p$ 是从 $j$ 开始第一个不等于 $s_j$ 的位置。

考虑从后往前 DP，设 $f_{i, j}$ 表示 $s_i = j$ 的方案数。计算 $f_{i, j}$ 时，枚举 $i'$ 表示 $s_{i\sim i' - 1}$ 相等且 $s_{i' - 1}\neq s_{i'}$，枚举 $j'\neq j$。考虑什么情况下 $f_{i, j}$ 可以从 $f_{i', j'}$ 转移过来：如果存在 $i\leq u < i' \leq v$ 要求 $T_u\leq T_v$，那么 $j$ 不能小于 $j'$；若要求 $T_u\geq T_v$，那么 $j$ 不能大于 $j'$。

设 $u < v$，则：

• 当有限制 $T_u\leq T_v$ 时，在 $u < i'\leq v$ 转移到 $u$ 之前的位置时，必须有 $j > j'$。

• 当有限制 $T_u\geq T_v$ 时，在 $u < i'\leq v$ 转移到 $u$ 之前的位置时，必须有 $j < j'$。

这说明，固定了 $i'$ 之后，随着 $i$ 不断向前移动，存在一个时刻使得 $i'$ 不再能产生 $j > j'$ 的贡献，也存在一个时刻使得 $i'$ 不再能产生 $j < j'$ 的贡献。

设 $h_j$ 表示 $f_{i + 1}\sim f_n$ 对之前的位置的每个 $j$ 产生的贡献。枚举到 $i$ 时，考虑所有和 $i$ 有关的限制 $(u, v)$（$u = i < v$）

• 若限制 $T_u\leq T_v$，那么对于所有 $u < i'\leq v$ 且仍产生 $j < j'$ 的贡献的 $i'$，将它 $j < j'$ 的贡献从 $h$ 中去掉，即令 $h_j$ 减去 $\sum_{j < j'} f_{i', j'}$。
• 若限制 $T_u\geq T_v$，那么对于所有 $u < i' \leq v$ 且仍产生 $j > j'$ 的贡献的 $i'$，将它 $j > j'$ 的贡献从 $h$ 中去掉，即令 $h_j$ 减去 $\sum_{j > j'} f_{i', j'}$。

更新 $h$ 之后有 $f_{i, j} = h_j + 1$，其中 $1$ 表示 $s_{i\sim n}$ 均相等的情况。统计 $f_i$ 对 $h$ 的贡献：$h_{j}$ 加上 $\sum_{j'\neq j} f_{i, j'}$。

用链表或栈维护两种情况仍产生贡献的 $i'$，时间复杂度 $\mathcal{O}(n|\Sigma|)$。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using LL = __int128_t;
using ui = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(20060130);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + \
  fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
  int x = 0;
  char s = getc();
  while(!isdigit(s)) s = getc();
  while(isdigit(s)) x = x * 10 + s - '0', s = getc();
  return x;
}

#define putc(x) putchar(x)
inline void print(ui x) {
  if(x >= 10) print(x / 10);
  putc(x % 10 + '0');
}

// ---------- templates above ----------

constexpr int N = 5e5 + 5;

int n, m, f[N][27], h[27];
int a[N], b[N], x[N], y[N];
vector<int> e[N], g[N];

void mian() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) a[i] = b[i] = i + 1;
  for(int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if(x < y) e[x].push_back(y);
    else g[y].push_back(x);
  }
  for(int i = n; i; i--) {
    for(int it : e[i]) {
      for(int p = a[i]; p <= it; p = a[p]) {
        vector<int> s(27);
        for(int j = 1; j <= 26; j++) s[j] = add(s[j - 1], f[p][j]);
        for(int j = 1; j <= 26; j++) addt(h[j], mod - add(s[26], mod - s[j]));
        a[i] = a[p];
      }
    }
    for(int it : g[i]) {
      for(int p = b[i]; p <= it; p = b[p]) {
        vector<int> s(27);
        for(int j = 1; j <= 26; j++) s[j] = add(s[j - 1], f[p][j]);
        for(int j = 1; j <= 26; j++) addt(h[j], mod - s[j - 1]);
        b[i] = b[p];
      }
    }
    int sum = 0;
    for(int j = 1; j <= 26; j++) {
      f[i][j] = h[j] + 1;
      addt(h[j], mod - f[i][j]);
      addt(sum, f[i][j]);
    }
    if(i == 1) cout << sum << "\n";
    for(int j = 1; j <= 26; j++) addt(h[j], sum);
  }
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  while(T--) mian();
  fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/