2020 Feb Records | fa

菜鸡 fa_555 会把一些动态简要地记在这里。主要还是留给自己以后看的。

所有代码不保证包括无关紧要的部分

【模板】三维偏序

CDQ 分治模板。

problem

有 $n$ 个三元组 $(a_i, b_i, c_i)$，设 $f(i) = \sum \limits_{j \ne i} [a_j \le a_i \land b_j \le b_i \land c_j \le c_i]$。

对于每个 $d \in [0, n)$，求 $f(i) = d$ 的数量。

solution

求序列逆序对还会吧？我们用归并排序进行分治，每次把区间 $[l, r]$ 分成 $[l, mid], (mid, r]$ 进行递归，在递归时计算 $[l, mid]$ 中对 $(mid, r]$ 的贡献。把下标和权值分别看作两个关键字，这就是二维偏序问题。

首先将序列按 $a$ 排序。分治时每次将左、右两区间分别按 $b$ 排序。此时左半边的 $a$ 均小于等于右半边。类似二维偏序，随便找个数据结构维护一下 $c$ 即可。

出现了新的问题：完全相同的元素，原本应当互相有贡献，但 cdq 分治只会计算左侧对右侧的贡献。给每个元素一个权值 $w$（同时维护这个值）。至于最后统计答案，想清楚统计的是什么。

code

int N, M, K, ans[100003];

struct Node {
  int a, b, c, w, cnt;
} s[100003], z[100003];

bool cmp1(const Node &l, const Node &r) {
  if (l.a != r.a) return l.a < r.a;
  if (l.b != r.b) return l.b < r.b;
  return l.c < r.c;
}

bool cmp2(const Node &l, const Node &r) {
  if (l.b != r.b) return l.b < r.b;
  return l.c < r.c;
}

namespace BIT {
int t[200003];

void add(int p, int v);
int query(int p);
}
using namespace BIT;

void CDQ(int l, int r) {
  if (l == r) return;
  int m = (l + r) >> 1;
  CDQ(l, m), CDQ(m + 1, r);
  std::sort(s + l, s + m + 1, cmp2);
  std::sort(s + m + 1, s + r + 1, cmp2);
  int i = l;
  for (int j = m + 1; j <= r; ++j) {
    for (; s[i].b <= s[j].b && i <= m; ++i)
      add(s[i].c, s[i].w);
    s[j].cnt += query(s[j].c);
  }
  for (int j = l; j < i; ++j)
    add(s[j].c, -s[j].w);
}

int main() {
  cin >> M >> K;
  for (int i = 1; i <= M; ++i)
    cin >> z[i].a >> z[i].b >> z[i].c;
  std::sort(z + 1, z + M + 1, cmp1);
  
  for (int i = 1, j = 1; i <= M; ++i, ++j)
    if (z[i].a != z[i + 1].a || z[i].b != z[i + 1].b
     || z[i].c != z[i + 1].c)
      s[++N] = z[i], s[N].w = j, j = 0;

  CDQ(1, N);
  for (int i = 1; i <= N; ++i)
    ans[s[i].cnt + s[i].w - 1] += s[i].w;

  for (int i = 0; i < M; ++i)
    cout << ans[i] << '\n';
  cout.flush();
  return 0;
}

【模板】基数排序

没啥好说的。不过我跟别人写得都不一样\dk。

int N, l[11], z[100003], c[10][100003];

int maxbit(int *z, int N) {
  int ans = 0, mx = *std::max_element(z + 1, z + N + 1);
  do ++ans; while (mx /= 10);
  return ans;
}

void rsort(int* z, int N) {
  int d = maxbit(z, N);
  for (int r = 1, n; d; --d, r *= 10) {
    n = 0;
    memset(l, 0, sizeof(int) * 10);
    for (int i = 1, t; i <= N; ++i) {
      t = z[i] / r % 10;
      c[t][++l[t]] = z[i];
    }
    for (int i = 0; i < 10; ++i)
      for (int j = 1; j <= l[i]; ++j)
        z[++n] = c[i][j], c[i][j] = 0;
  }
}

【模板】后缀排序

~~没看懂，背代码~~

咕咕咕 // TODO

#include<cstdio>
#include<cstring>
#include<iostream>

using iarrN = int[100003];

char s[100003];
int N, M;
iarrN c, rnk, sa, t, H;

void rSort() {
  memset(c + 1, 0, sizeof(int) * M);

  for (int i = 1; i <= N; ++i)
    ++c[rnk[i]];
  for (int i = 2; i <= M; ++i)
    c[i] += c[i - 1];
  for (int i = N; i; --i)
    sa[c[rnk[t[i]]]--] = t[i];
}

void sufSort() {
  M = 'z' - '0' + 1; // 75
  for (int i = 1; i <= N; ++i)
    rnk[i] = s[i] - '0' + 1, t[i] = i;
  rSort();
  M = 0;
  for (int w = 1; M < N; w <<= 1) {
    M = 0;
    for (int i = N - w + 1; i <= N; ++i)
      t[++M] = i;
    for (int i = 1; i <= N; ++i)
      if (sa[i] > w) t[++M] = sa[i] - w;
    rSort();
    memcpy(t + 1, rnk + 1, N << 2);
    rnk[sa[1]] = M = 1;
    for (int i = 2; i <= N; ++i)
      rnk[sa[i]] = (t[sa[i - 1]] == t[sa[i]]
        && t[sa[i - 1] + w] == t[sa[i] + w]) ? M : ++M;
  }
  for (int i = 1, j = 0; i <= N; ++i) {
    if (rnk[i] == 1) continue;
    while (s[i + j] == s[sa[rnk[i] - 1] + j])
      ++j;
    H[rnk[i]] = j;
    if (j) --j;
  }
}

int main() {
  fread(s + 1, 1, 100000, stdin);
  N = strlen(s + 1);
  while (s[N] < 48) --N;
  sufSort();
  for (int i = 1; i <= N; ++i)
    std::cout << sa[i] << ' ';
  std::cout << '\n';
  for (int i = 0; i <= N; ++i)
    std::cout << H[i] << ' ';
  return 0;
}

[NOI2015]品酒大会

咕咕咕 // TODO

code

/* struct IO { ... } cout; */

using iarrN = int[300003];
using ll = long long;

constexpr ll inf = 1e18;

char s[300003];
int N;
std::vector<int> v[300003];

namespace SA {
int M;
iarrN H, sa, rnk, c, t, z;
ll now, sum = -inf, ans1[300003], ans2[300003];

void rSort();
void sufSort();
} // SA
using namespace SA;

namespace DSU {
iarrN fa, siz, mx, mn;

int find(int u); // 路径压缩

void merge(int u, int v) {
  u = find(u), v = find(v);
  now += 1ll * siz[u] * siz[v];
  sum = std::max(sum, (std::max(1ll * mx[u] *  mx[v], 1ll * mn[u] * mn[v])));
  if (siz[u] > siz[v]) std::swap(u, v);
  fa[u] = v, siz[v] += siz[u];
  mx[v] = std::max(mx[u], mx[v]);
  mn[v] = std::min(mn[u], mn[v]);
}
} // DSU
using namespace DSU;

int main() {
  // 这个并查集属实没想出来
  // 感谢 @Nemlit 的题解，太棒了，学到许多
  scanf("%d\n", &N);
  fread(s + 1, 1, N, stdin);
  for (int i = 1; i <= N; ++i)
    scanf("%d", z + i);
  sufSort();
  for (int i = 1; i <= N; ++i) {
    fa[i] = i, siz[i] = 1;
    mx[i] = mn[i] = z[sa[i]];
    v[H[i]].push_back(i);
  }
  for (int i = N - 1; i >= 0; --i) {
    for (int k : v[i]) merge(k, k - 1);
    if (now) ans1[i] = now, ans2[i] = sum;
  }
  for (int i = 0; i < N; ++i)
    cout << ans1[i] << ' ' << ans2[i] << '\n';
  cout.flush();
  return 0;
}

【模板】单调栈

水题。随手写了一发~~，目前(02-06 23:40)最优解第五。~~，目前(02-23 21:50) 更新了数据，重交后最优解第一。

problem

给定一个长为 $N$ 的序列 $a$。对于每个元素，求其后第一个大于 $a_i$ 的元素的下标。

solution

对序列中元素的下标和值维护一个栈。对于每个元素，每当栈顶小于当前元素，记录栈顶所在当前下标的答案并弹栈；最后将当前元素压入栈。

【模板】乘法逆元2

~~鱼说是卡常，实际上是卡了个能过的高复杂度~~

~~卡完之后这题和逆元几乎没关系了~~

problem

给定长为 $n$ 的正整数序列 $a$ 与常数 $k, p(p \in \mathbb{P})$，求

$\sum_{i = 1}^n \frac{k^i}{a_i}$

在模 $p$ 意义下的值。

solution

直接算复杂度是 $O(n \log p)$，差不多能过~~，但是完全被卡掉了~~。

考虑瞎推式子。设 $\mathrm{Pre}_i$ 表示前 $i$ 个数的前缀积，$\mathrm{Suf}_i$ 表示后 $i$ 个数的后缀积。暴力通分可得所求答案为

$\frac{\sum \limits_{i = 1}^n k^i \mathrm{Pre}_{i - 1} \mathrm{Suf}_{i + 1}}{\mathrm{Pre}^n}$

。时间复杂度 $O(n)$。跑得挺快~~，然而大空间选手震怒~~。

抄来的 $O(1)$ 龟速乘（？）

~~抄的 scape 抄的 dls 的~~

前两个特判是为了避免 $m$ 较小时出错。

适用于两个 ll 范围内的数相乘模一个 ll 范围内的数。

using ll = long long;
using ldb = long double;

inline ll Mul(ll a, ll b, ll m) {
  a %= m, b %= m;
  if (m <= 1000000000) return a * b % m;
  if (m <= 1000000000000)
    return (((a * (b >> 20) % m) << 20) + a * (b & ((1 << 20) - 1))) % m;
  ll d = floor(a * (ldb)b / m + 0.5);
  ll ans = (a * b - d * m) % m;
  if (ans < 0) ans += m;
  return 0;
}

【模板】Johnson 全源最短路

problem

给定一个有向图，求任意两点间的最短路。

这个图有以下特点：

有负权、重边和自环。需要判断有无负环。
数据范围 floyd 过不去。
跑 n 次 spfa 会被卡。

solution

建立一个超级源点 $S$，向每个点 $i$ 连边 $(S, i, 0)$。
- 相当于在 spfa 开始直接将所有点入队。
用 spfa（或 Bellman-Ford）求出求出 $S$ 到其他各点 $i$ 的最短路 $d_i$。判断负环在这一步进行。
将每条边 $(u, v, w)$ 改为 $(u, v, w + h_u - h_v)$。
- 此时图中不存在负权。
用 $n$ 次 dijkstra 求出任意两点间的最短路。
- 别忘了把真实的边权改回去。若求出的距离为 dis_[u][v]，实际距离为 dis[u][v]，则 dis[u][v] = dis_[u][v] - h[u] + h[v]。

code

有一说一，有点细节。

using ll = long long;

constexpr int inf = 0x3f3f3f3f;

std::bitset<3003> vis;
int N, M, tot, cnt[3003], head[3003], dis[3003], d[3003];

struct Edge {
  int nxt, to, w;
} e[6003];

void addEdge(int u, int v, int w);
bool spfa();
void dijkstra(int s);

int main() {
  cin >> N >> M;
  for (int u, v, w; M; --M) {
    cin >> u >> v >> w;
    addEdge(u, v, w);
  }
  if (!spfa()) return puts("-1"), 0;
  for (int i, u = 1; u <= N; ++u)
    for (i = head[u]; i; i = e[i].nxt)
      e[i].w += d[u] - d[e[i].to];
  for (int i = 1; i <= N; ++i) {
    dijkstra(i);
    ll ans = 0;
    for (int j = 1; j <= N; ++j)
      if (dis[j] == inf) ans += j * 1000000000ll;
      else ans += 1ll * j * (dis[j] - d[i] + d[j]);
    cout << ans << '\n';
  }
  cout.flush();
  return 0;
}

【模板】康托展开

problem

给定 $1 \sim N$ 的一个排列 $P$，求它在 $1 \sim N$ 的所有排列中的排名。

solution

从前向后枚举 $P$ 的每个位置。对于第 $i$ 个位置，若它是还未使用的数中第 $j$ 小的，则对答案的贡献为 $(N - i)! \times (j - 1)$。

由于最终答案要求排名，所以要加 $1$。

【模板】树上 k 级祖先

长链剖分，久仰大名。~~其实跟重剖也没啥区别~~

solution

预处理，$O(n \log n)$
1. 树上倍增求出每个点的 $2^n$ 级祖先。$O(n \log n)$。
2. 对树进行长剖，对于每个点记录所在链的顶点和深度；对于每条链，若其长度为 $l$，则在其顶点处记录向上的 $l$ 个祖先和向下的 $l$ 个链上的儿子。$O(n)$。
  - 可以使用 std::vector 实现。
  - 也可利用 dfs 序，魔改 dfs，通过两个数组保存。速度当然是要比 vector 快的。
询问 $u$ 的 $k$ 级祖先，单次 $O(1)$
1. 先利用倍增数组跳到 $u$ 的 $2^{\lfloor \log_2 k \rfloor}$ 级祖先。其中 $\lfloor \log_2 k \rfloor$ 也可 $O(n)$ 预处理出。
2. 若剩余 $k’$ 级，显然有 $k’ < 2^{\lfloor \log_2 k \rfloor}$。则当前链长 $\ge 2^{\lfloor \log_2 k \rfloor} > k’$。因此可以先跳到此时所在链的顶点。根据剩余 $k$ 的正负，分别用向上、向下的数组求出答案。

总复杂度 $O(n \log n + q)$。

code

这个魔改的邪教 dfs2 传了三个参。注意由于原题性质，这里 dfs 时没有判爹。

void dfs1(int u) {
  for (int i = 1; i <= 18; ++i)
    fa[u][i] = fa[fa[u][i - 1]][i - 1];
  mxd[u] = dep[u] = dep[fa[u][0]] + 1;
  for (int i = head[u], v; i; i = e[i].nxt) {
    dfs1(v = e[i].to);
    if (dmax(mxd[u], mxd[v])) son[u] = v;
  }
}

void dfs2(int u, int t, int up) {
  top[u] = t;
  dfn[u] = ++dft, D[dft] = u, U[dft] = up;
  if (!son[u]) return;
  dfs2(son[u], t, fa[up][0]);
  for (int i = head[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != son[u])
      dfs2(v, v, v);
}

int query(int u, int k) {
  if (!k) return u;
  u = fa[u][lg[k]];
  k -= (1 << lg[k]) + dep[u] - dep[top[u]];
  u = top[u];
  return k >= 0 ? U[dfn[u] + k] : D[dfn[u] - k];
}

【模板】无向图三元环计数

solution

首先给每条边定向：度数小的连向度数大的，度数相等则编号小的连向编号大的。

枚举每个点、它的出边、它的出边的出边，暴力统计答案。

复杂度是 $O(m \sqrt m)$ 的~~，不会证不会证~~。

SP10395 ABA12D - Sum of divisors!

这题有一些很棒的东西，不过这篇题解的做法中规中矩。

有时间探索一下那个奇妙的做法。

46789 51939 54515 49653 48818

【模板】笛卡尔树

problem

给定一个 $1 \sim n$ 的排列 $p$，构建一棵二叉树，满足：

每个结点的编号满足二叉搜索树的性质。
结点 $i$ 的权值为 $p_i$，每个结点的权值满足小根堆的性质。

solution

这棵二叉树即为这个序列的笛卡尔树。它有以下性质：

它的中序遍历是原序列。
任意一个结点的值都大于它的两个儿子的值。
两个点的 lca 就是他们的 RMQ。

构造方法：

维护一个单调栈，按顺序插入每一个元素，每个元素包含值和序号两个信息。
每当栈顶元素 $v$ 的值大于当前元素 $u$ 的值，弹出 $v$ 并将其设为 $u$ 的左儿子。否则将 $u$ 设为 $v$ 的右儿子。最后将 $u$ 入栈。
最终栈顶元素的序号为树根。

code

s[] 存储编号，w[] 存储值。

for (int i = 1, t; i <= N; ++i) {
  cin >> t;
  while (top && t < w[top]) ls[i] = s[top--];
  if (top) rs[s[top]] = i;
  s[++top] = i, w[top] = t;
}

【模板】Prufer 序列

Prufer 序列与带标号无根树的相互转化

Prufer 序列可以将一个带标号 $n$ 个结点的树用 $[1, n]$ 中的 $n - 2$ 个整数表示。也可以理解为完全图的生成树与数列之间的双射。

Prufer 是这样建立的：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n - 2$ 次后就只剩下两个结点，算法结束。

重建树的方法是类似的。根据 Prufer 序列的性质，我们可以得到原树上每个点的度数。然后你也可以得到度数最小的叶结点编号，而这个结点一定与 Prufer 序列的第一个数连接。然后我们同时删掉这两个结点的度数。

void solve1() { // tree -> prufer code
  for (int i = 1; i < N; ++i)
    cin >> f[i], ++d[f[i]];
  for (int i = 1, j = 1; i <= N - 2; ++i, ++j) {
    while (d[j]) ++j;
    for (p[i] = f[j]; i <= N - 2 && !--d[p[i]] && p[i] < j; ++i)
      p[i + 1] = f[p[i]];
  }
}

void solve2() { // prufer code -> tree
  for (int i = 1; i <= N - 2; ++i)
    cin >> p[i], ++d[p[i]];
  p[N - 1] = N;
  for (int i = 1, j = 1; i < N; ++i, ++j) {
    while (d[j]) ++j;
    for (f[j] = p[i]; i < N && !--d[p[i]] && p[i] < j; ++i)
      f[p[i]] = p[i + 1];
  }
}

Prufer 序列的性质

在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点 $n$。
每个结点在序列中出现的次数是其度数减 $1$。（没有出现的就是叶结点）
通过 Prufer 序列显然有结论：完全图 $K_n$ 有 $n^{n - 2}$ 棵生成树。

Reference

Prufer 序列 - OI Wiki

CF156D Clues

problem

一个 $n$ 个点 $m$ 条边的带标号无向图有 $k$ 个连通块。我们希望添加 $k - 1$ 条边使得整个图连通。求方案数。

solution

前置知识：多重组合数

设 $s_i(1 \le i \le k)$ 表示第 $i$ 个联通块中的点数。设 $d_i$ 为构造的连通图中第 $i$ 个连通块的度数。显然有 $\sum_{i = 1}^k d_i = 2k - 2$。则对于给定的 $d$ 序列构造 Prufer 序列的方案数是

$\binom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} = \frac{(k - 2)!}{\prod_{i = 1}^k (d_i - 1)!}$

对于第 $i$ 个联通块，它对外连接的方式有 $s_i^{d_i}$ 种，因此对于给定 $d$ 序列使图联通的方案数是

$\binom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} \times \prod_{i = 1}^k s_i^{d_i}$

然后我们要枚举 $d$ 序列，式子变成

$\sum_{d_i \ge 1, \sum_{i = 1}^k d_i = 2k - 2} \binom{k - 2}{d_1 - 1, d_2 - 1, \cdots, d_k - 1} \times \prod_{i = 1}^k s_i^{d_i}$

对于处理这个式子，我们有多元二项式定理
$(\sum_{i = 1}^m x_i)^p = \sum_{c_i \ge 0, \sum_{i = 1}^m c_i = p} \binom{p}{c_1, c_2, \cdots, c_m} \times \prod_{i = 1}^m x_i^{c_i}$

令 $e_i = d_i - 1$，那么显然有 $\sum_{i = 1}^k e_i = k - 2$，于是式子成为

$\begin{aligned} &\sum_{e_i \ge 0, \sum_{i = 1}^k e_i = k - 2} \binom{k - 2}{e_1, e_2, \cdots, e_k} \times \prod_{i = 1}^k s_i^{e_i + 1} \\ =& (\sum_{i = 1}^k s_i)^{k - 2} \times \prod_{i = 1}^k s_i \\ =& n^{k - 2} \times \prod_{i = 1}^k s_i \end{aligned}$

这个式子就很好求了。并查集统计一下即可，可以写成 $O(n \alpha(n))$ 的。

Reference

Prufer 序列 - OI Wiki

【模板】EXCRT

problem

给定 $n$ 组非负整数 $m_i, r_i$，求解关于 $x$ 的方程组的最小非负整数解。

其中方程组中的第 $i(1 \le i \le n)$ 个方程为

$x \equiv r_i \pmod{m_i}$

solution

中国剩余定理就是垃圾。

直接跑 $n$ 次 exgcd 可以在 $O(n \log n)$ 的时间内解决这个问题，并且不要求 $m_i$ 两两互质。

code

using ll = long long;

inline ll Mod(ll b, ll m);
inline ll Mul(ll b, ll p, ll m);
void exgcd(ll a, ll b, ll &g, ll &x, ll &y);

ll N, m[100003], r[100003];

ll EXCRT() {
  ll M = 1, ans = 0, a, b, c, x, y, g;
  for (int i = 1; i <= N; ++i) {
    a = M, b = m[i], c = Mod(r[i] - ans, b);
    exgcd(a, b, g, x, y);
    // if (c % gcd) return -1;
    ans += Mul(x, c / g, b / g) * M;
    ans = Mod(ans, M *= b / g);
  }
  return Mod(ans, M);
}

int main() {
  cin >> N;
  for (int i = 1; i <= N; ++i)
    cin >> m[i] >> r[i];
  printf("%lld", EXCRT());
  return 0;
}

AT1219 歴史の研究

第一道回滚莫队题目。

problem

给定长为 $n (1 \le n \le 10^5)$ 的序列 $a (1 \le a_i \le 10^9, 1 \le i \le n)$ 和 $q (1 \le q \le 10^5)$ 组询问 $l_i, r_i$。

每次询问 $\max_{i = l}^r a_i \times t_{a_i}$，其中 $t_x$ 表示 $x$ 在 $a_{l..r}$ 中的出现次数。

solution

不需要支持修改，考虑离线算法。发现统计的区间容易扩展而难以删除，于是考虑回滚莫队：

预处理，$O(n \log n + q \log q)$
- 序列分块，本题需要离散化，$O(n \log n)$
- 对询问进行排序，$O(q \log q)$
莫队，对每个块分别处理左端点在该块内的询问，$O(n \sqrt n)$
- 第 $i$ 个块右端点为 $R_i$，初始设左指针为 $R_i + 1$，右指针为 $R_i$ 表示空区间
- 对于 $r$ 在块内的询问（或 $r - l \le \sqrt n$ 的询问），暴力统计
- 向右扩展区间直到右指针到达当前询问的 $r$，并记录当前的答案
- 采取手段向左扩展，同时不对向右扩展记录的数据产生影响
- 记录该次询问的答案，并采取手段还原为向左扩展前的状态
- 容易想到这样~~通过牺牲常数~~做到了 $O(n \sqrt n)$ 的复杂度

code

好像写得非常不容易理解，还是看代码吧（

写的时候注意头脑清醒，同时注意不要滥用 memset 系函数。

我相信你能看懂自己的变量名。

inline void add(int p) {
  now = std::max(now, 1ll * ++c[z[p]] * z_[z[p]]);
}

ll solve(int l, int r) {
  ll ans = 0;
  for (int i = l; i <= r; ++i)
    ans = std::max(ans, 1ll * ++c_[z[i]] * z_[z[i]]);
  for (int i = l; i <= r; ++i)
    --c_[z[i]];
  return ans;
}

void process() {
  for (int i = 1, j = 1, l, r; i <= num && j <= M; ++i) {
    memset(c + 1, 0, sizeof(int) * N);
    r = R[i];
    now = 0;
    for (; bel[q[j].l] == i; ++j) {
      if (q[j].r < r) {
        ans[q[j].id] = solve(q[j].l, q[j].r);
        continue;
      }
      l = R[i] + 1;
      while (r < q[j].r) add(++r);
      ll t = now;
      while (l > q[j].l) add(--l);
      ans[q[j].id] = now, now = t;
      while (l <= R[i]) --c[z[l++]];
    }
  }
}

【模板】回滚莫队

比上面一道难写多了。写法是自己想的。

为什么我写数据结构常数这么大啊（哭）

problem

给定长为 $n (1 \le n \le 2 \times 10^5)$ 的序列 $a (1 \le a_i \le 2 \times 10^9, 1 \le i \le n)$ 和 $q (1 \le q \le 2 \times 10^5)$ 组询问 $l_i, r_i$。

每次询问 $a_{l..r}$ 中相同的数的最大下标差。

code

没啥好说的，看你自己的代码吧。

inline void addR(int p) {
  dmax(mx[z[p]], p);
  dmin(mn[z[p]], p);
  dmax(now, mx[z[p]] - mn[z[p]]);
}

inline void addL(int p) {
  dmax(mx_[z[p]], mx[z[p]]);
  dmax(mx_[z[p]], p);
  dmin(mn_[z[p]], mn[z[p]]);
  dmin(mn_[z[p]], p);
  dmax(now, mx_[z[p]] - mn_[z[p]]);
}

inline void delL(int p) {
  mx_[z[p]] = 0;
  mn_[z[p]] = inf;
}

int solve(int l, int r) {
  int ans = 0;
  for (int i = l; i <= r; ++i) {
    dmax(mx_[z[i]], i);
    dmin(mn_[z[i]], i);
    dmax(ans, mx_[z[i]] - mn_[z[i]]);
  }
  for (int i = l; i <= r; ++i)
    mx_[z[i]] = 0, mn_[z[i]] = inf;
  return ans;
}

void process() {
  memset(mn_ + 1, 0x3f, sizeof(int) * N);
  for (int i = 1, j = 1, t, l, r; i <= num && j <= M; ++i) {
    memset(mx + 1, 0, sizeof(int) * N);
    memset(mn + 1, 0x3f, sizeof(int) * N);
    r = R[i];
    now = 0;
    for (; bel[q[j].l] == i; ++j) {
      if (q[j].r < r) {
        ans[q[j].id] = solve(q[j].l, q[j].r);
        continue;
      }
      l = R[i] + 1;
      while (r < q[j].r) addR(++r);
      t = now;
      while (l > q[j].l) addL(--l);
      ans[q[j].id] = now, now = t;
      while (l <= R[i]) delL(l++);
    }
  }
}

CF1285D Dr. Evil Underscores

problem

给出 $n (1 \le n \le 10^5)$ 个数 $a_i (0 \le a_i \le 2^{30} - 1)$，找到 $x$ 使得 $\max_{i = 1}^n a_i \oplus x$ 最小。求出这个最小值。

solution

~~动脑子会以为是二分，但这显然就是 Trie 大水题~~

建出 01-Trie，在 Trie 上 dfs（树形 dp）：

设当前结点为 $u$，在数字从低到高第 $c$ 位
令 $s$ 为递归处理 $\mathrm{nxt}_{u, 0}$ 与 $\mathrm{nxt}_{u, 1}$ 返回答案的较小值。
若 $u$ 的两个儿子都存在，则答案为 $s + 2^c$，否则答案为 $s$。

代码很丑，就不放了。

AGC004C AND Grid

problem

给定一个网格图，有些位置已经被涂色。要求构造两个相同大小的网格图，并且在上面涂色，需要保证颜色四连通，且满足这两个网格的涂色部分的重合位置恰好是给定的网格图的涂色位置。题目保证边界上不会被涂色。

solution

维护两个网格图，都初始化为原网格图。将第一个网格图的第一列和奇数行（除最后一列）全部染色；第二个网格图的最后一列和偶数行（除第一列）全部染色。

容易想到这样是对的。

数列分块入门 9

🐴的，没想到我一直咕掉的数列分块 9 是回滚莫队板子（

CF576C Points on Plane

problem

给出 $n (1 \le n \le 10^6)$ 个点 $(x_i, y_i) (0 \le x_i, y_i \le 10^6)$，求一个排列 $p$，使得 $\sum_{i = 2}^n |x_{p_i} - x_{p_{i - 1}}| + |y_{p_i} - y_{p_{i - 1}}| \le 2.5 \times 10^9$。

solution

依据莫队的分块思想进行排序，算一下会发现这样最多会跳 $3 \times 10^9$。加一个奇偶排序，最多就成了 $2 \times 10^9$，很稳。

CF679A Bear and Prime 100

大水题，没啥好说的。这是我的第一道交互题。

CF727C Guess the Array

一眼秒。从这题知道了可以一次输出进行多次询问（只需在最后 flush 一次），也可将多次询问的回答一起读入。可以关同步。可以 ::tie。

CF730B Minimum and Maximum

problem

这是一道交互题。输入有 $T (1 \le T \le 1000)$ 组数据。

有一个长度为 $n (1 \le n \le 50)$ 的序列，你需要求出最小数和最大数的编号。每次可以询问序列中两个数的相对大小，最多可以询问 $\lceil \frac{3n}{2} \rceil - 2$ 次。

solution

朴素的想法是把序列 $O(n)$ 地扫一遍。这样的比较次数是 $2n - 2$，会超过限制。优化很简单：每次取相邻的两个元素比较大小，再分别将较大者与当前的最大值比较；将较小者与当前的最小值比较。这样将原先 $4$ 次的询问优化成了 $3$ 次，恰好符合要求。

code

char ask(int u, int v) {
  char c;
  cout << '?' << ' ' << u << ' ' << v << endl;
  cin >> c;
  return c;
}

int main() {
  int T, N, mx, mn;
  for (cin >> T; T; --T) {
    cin >> N;
    if (N & 1) mx = mn = 1;
    else {
      if (ask(1, 2) == '<') mn = 1, mx = 2;
      else mn = 2, mx = 1;
    }
    for (int i = 3 - (N & 1), u, v; i <= N; i += 2) {
      u = i, v = i + 1;
      if (ask(u, v) == '>') std::swap(u, v);
      if (ask(u, mn) == '<') mn = u;
      if (ask(v, mx) == '>') mx = v;
    }
    cout << '!' << ' ' << mn << ' ' << mx << endl;
  }
  return 0;
}

CF750F New Year and Finding Roots

一上午没做出来，我是傻逼。

CF896B Ithea Plays With Chtholly

我觉得这题翻译⑧太对劲，所以我不会做，也想不到题解为啥是对的（

P2153 [SDOI2009]晨跑

problem

有一个 $N$ 个点 $M$ 条边的有向图。找出若干条 $1 \sim N$ 的互不相交路径，使得这些路径条数尽量多且总长度尽量短。s

solution

~~有限制条件的最短路，显然是网络流。~~对于每个点只能经过一次的限制条件，通过拆点解决。

对每个点拆点 $i, i’$，连边 $(i, i’, 1, 0)$；对于原图中的边 $(u, v, w)$，连边 $(u, v, 1, w)$，超级源、汇分别为 $1’, N$，跑最小费用最大流即可。

复习专题

这部分是 fa_555 的复习。不对外公布。

见 _workspace\review\ 目录下 Treap.cpp, FHQ-Treap.cpp, FHQ-Treap2.cpp, Splay.cpp, Miller_Rabin.cpp。