「Summary」2023-07-04 做题记录

Posted on 2023-07-06

zxy 的大餐（双关）

😍😍😍

2023-07-04

CF679E

从最难处理的操作入手，如何判断一个区间中存在 $42$ 的次幂？如果单纯地去维护每个数的真实值，则会出现问题：没有一个统一的标准检验是否是 $42^{x}$ ，因为每个数处于不同的由 $42$ 的次幂分割出来的区间之中。
转换一下，维护每个数与它最近的 $42$ 次幂的差值，这样我们只需要检验数列中是否存在 $0$ 就行了。
出现另外一个问题，在重复做 3 操作的过程中有可能出现负数，这意味着这个数跨越了一个 $42$ 的次幂，我们必须单独去更新它。
考虑这个做法的复杂度， $42$ 的次幂在可能的值域中 $V = max {a_{i}} \times q = 1 e 14$ 最大只能在 $9$ 次方左右，也就是说，每个数最多只会跨过 $9 = \log_{42} V$ 次，但是做 2 操作会出现 $Θ (1)$ 个连续段，增加 $\log_{42} V$ 的势能，结合到每次操作是 $Θ (\log n)$ 的，所以总的时间复杂度是 $Θ ((q + n) \log_{42} V \log n)$ 。

NOI 2021 密码箱

首先看到 $f$ 的计算方式很有特色，可以看成是函数的复合。
于是整道题看成从左往右依次右乘一堆矩阵。
题目中有明显地增加序列长度的操作，那么假设现在拿到了增加前的答案为 $(x, y)$ ，写成向量的形式 $[\begin{matrix} x \\ y \end{matrix}]$ ，如果增加一个操作 w 或 e，把它看成对 $[\begin{matrix} x \\ y \end{matrix}]$ 进行一次线性变换。

首先推 w， $[\begin{matrix} x \\ y \end{matrix}] ⟶ [\begin{matrix} x + y \\ x \end{matrix}]$ ，得到 $w = [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]$ 。
对于 e，似乎需要分类讨论，但是如果需要分讨那么这个做法是做不了的，于是猜想一下不论末尾是不是 $1$ ，都可以共用一个矩阵 $e$ ，操作一次相当于增加了 $[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}]$ ，手算一下 $e = [\begin{matrix} 2 & - 1 \\ 1 & 0 \end{matrix}]$ 。

因为有操作 $2, 3$ 好像需要维护很多平衡树？其实不用，对于一个矩阵 $[\begin{matrix} a & b \\ c & d \end{matrix}]$ 通过简单解方程得到：

\begin{matrix} (1) & \begin{array}{r} f l i p ([\begin{array}{c} a & b \\ c & d \end{array}]) = [\begin{array}{c} a - b & - b \\ - a + b - c + d & b + d \end{array}] \\ r e v e r s e ([\begin{array}{c} a & b \\ c & d \end{array}]) = [\begin{array}{c} d - 2 c & - 2 a + b - 4 c + 2 d \\ c & a + 2 c \end{array}] \end{array} \end{matrix}

于是这样得到了一个常数比较小并且可以只用维护一颗平衡树的做法。

UOJ515 【UR #19】前进四

第一眼看上去可以 $Θ (n \log^{2} n)$ 的复杂度做线段树维护单调栈，但是只有 70pts。
思考去描述一下当前思路：以位置为主体，移动时间轴，扫描询问。
考虑切换主体，以时间为主体，从后往前移动位置，维护询问的数据结构。
修改变成了对一段询问区间取 $min$ ，询问变成了对于某个询问单点求 $min$ 值的变化次数。
用势能线段树维护，在修改的时候记一个变化次数的标记，复杂度 $Θ (n \log n)$ 。

UOJ671 【UNR #5】诡异操作

DJNB！！！！！！1
只有除的操作是一道经典题，加上取 $&$ 可以比较套路地想到把每个位置拆开，于是这个做法是 $Θ (n \log V \log n)$ 的，然后 $\log V$ 非常丑陋，最大取到 $128$ 。
想一想上面这个做法维护了个啥？相当于维护了一个 $\log V \log n$ 的 $0 / 1$ 矩阵。
描述当前思路，我们对于每个值维护了它出现的次数，是在用范围为 $\log V$ 的东西作为维度去维护范围为 $\log n$ 的东西。
考虑切换主体，我们尝试用范围为 $\log n$ 的东西作为维度去维护 $\log V$ 的东西，描述它，我们对于每种次数，维护出现过这么多次的值。
于是做法马上变成了 $Θ (n \log^{2} n)$ 的，具体实现只能说 DJNB。

CF1588F

好神的题，但也并非没有突破口。
发现这里既有图上的又有序列上的操作，非常抽象🤔，思考能不能分块，对谁分块。
因为操作过于复杂，那就对操作分块，于是我们现在得到了 $\sqrt{q}$ 个块，每个块里面有 $\sqrt{q}$ 个操作，我们需要在 $Θ (n)$ 左右的复杂度内解决每个块里的询问。
最恶心的操作是操作 3，出现了改边。结合到分块的原理，块内的元素相当于是等价的，他们的行为是平行的，而在操作 3 里面出现的点都经历了改边的步骤，所以他们的行为一定互相不平行，钦定他们为关键点，记换上的一部分为 $v_{1}, v_{2}, \dots, v_{k}, x, v_{k + 2}, v_{k + 3}, \dots, y, \dots$ ，其中 $x$ 和 $y$ 是被标记的关键点，那么可以知道 $v [1 \dots x]$ 可以放在一个块里面， $v [k + 2, y]$ 可以放在一个块里。
就像是这样

怎么想到的，为啥是对的？
其实很明显，因为 $x, y$ 有改边的操作，那么对于环上连在 $x$ 后面的点来说， $x$ 可以作为一个 leader， $x$ 后面的点的行为都是由 $x$ 指挥进行的。简单看一下，对于每一次拎出来的 $\sqrt{q}$ 操作，最多会有 $2 \sqrt{q}$ 个 leader 出现，意味着块的个数是 $\sqrt{q}$ 级别的。
这样看起来复杂度就对了，于是思考操作一怎么做，可以拆开一个询问，把区间和变成前缀和做差，那么只需要统计每个块中有多少个点出现在了询问中即可，这一步是 $Θ (n)$ 的。
操作二直接跳环上关键点，这一步是 $Θ (\sqrt{n})$ 的，操作三直接改即可。
因为 $n, q$ 同阶，所以总的复杂度是 $Θ (n \sqrt{n})$ 的。

代码确实不好写，还要多看几遍。

/*
If the radiance of a thousand suns were to burst into the sky?
...that would be like the splendor of the mighty one.
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 600;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int n, q, m, cnt, siz, ind, tp,nxt[MAXN], col[MAXN], ed[MAXN], stk[MAXN];
struct Node { int opt, x, y, ind; } que[MAXN], ask[MAXN];
vector<int> pos;
bool vis[MAXN];
LL sum[MAXN], add[MAXN], num[MAXM][MAXM], a[MAXN];

inline void solve(int m) {

  ind = 0, cnt = 0, pos.clear();
  memset(vis, 0, sizeof(vis)), memset(col, 0, sizeof(col));
  memset(num, 0, sizeof(num)), memset(add, 0, sizeof(add));
  for (int i = 1; i <= m; i++) {
    if (que[i].opt == 1) {
      if (que[i].x > 1) ask[++cnt] = Node{-1, que[i].x - 1, 1, i};
      ask[++cnt] = Node{+1, que[i].y, 1, i};
    } else if (que[i].opt == 2) vis[que[i].x] = true;
    else vis[que[i].x] = vis[que[i].y] = true;
  }

  for (int i = 1, now; i <= n; i++) if (vis[i]) {
    pos.push_back(i), now = i;
    do { stk[++tp] =  nxt[now], now = nxt[now]; } while (vis[now] != true);
    ed[pos.size()] = stk[tp]; while (tp) col[stk[tp--]] = ed[pos.size()];
  }
  sort(ask + 1, ask + 1 + cnt, [](const Node& x, const Node& y) { return x.x < y.x; });

  for (int i = 1; i <= cnt; i++) {
    while (ind < ask[i].x) add[col[++ind]]++;
    for (int j = 1; j <= (int)pos.size(); j++) num[ask[i].ind][j] += ask[i].opt * add[ed[j]];
  }

  memset(add, 0, sizeof(add));
  for (int i = 1, now; i <= m; i++) {
    if (que[i].opt == 1) {
      LL res = sum[que[i].y] - sum[que[i].x - 1];
      for (int j = 1; j <= (int)pos.size(); j++) res += num[i][j] * add[col[ed[j]]];
      printf("%lld\n", res);
    } else if (que[i].opt == 2) {
      now = col[que[i].x];
      do { add[now] += que[i].y, now = col[nxt[now]]; } while (now != col[que[i].x]);
    } else swap(nxt[que[i].x], nxt[que[i].y]);
  }
  for (int i = 1; i <= n; i++) a[i] += add[col[i]], sum[i] = sum[i - 1] + a[i];

}

int main() {

  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), sum[i] = sum[i - 1] + a[i];
  for (int i = 1; i <= n; i++) read(nxt[i]);

  read(q), siz = sqrt(q);
  for (int i = 1; i <= q; i++) {
    m++, read(que[m].opt, que[m].x, que[m].y);
    if (m == siz) solve(m), m = 0;
  }
  if (m > 0) solve(m);

  return 0;
}

The End

「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」