2020 PKU WC 数论构造大赛

简要题意：

有一个 \(n \times m\) \((1 \le n, m \le 50\ 000)\) 的矩阵。实现一个数据结构，支持以下操作。

先进行 \(q_1\) \((1 \le q_1 \le 50\ 000)\) 次修改 s l r x，表示对所有与 \(s\) 互质的行，\([l,r]\) 列上加上 \(x\)。

再进行 \(q_2\) \((1 \le q_2 \le 100\ 000)\) 次查询 s l r，求所有与 \(s\) 互质的行中，\([l,r]\) 列上的和，对 \(2^{32}\) 取模。

保证 \(s\) 在 \([1, n]\) 中随机。

1s, 1024 MB.

挂一份吉老师给的题解：

考虑所有修改 \(s_i, l_i, r_i, x_i\) 对询问 \(s, l, r\) 的贡献。

\[ \begin{aligned} & \sum_{i = 1} ^ {q_1} \operatorname{overlap}(l_i, r_i, l, r) x_i \sum_{j = 1} ^ n [\gcd(s_i, j) = 1][\gcd(s, j) = 1] \\ =& \sum_{i = 1} ^ {q_1} \operatorname{overlap}(l_i, r_i, l, r) x_i \sum_{j = 1} ^ n \left( \sum_{d_1 \vert \gcd(s_i, j)} \mu(d_1) \sum_{d_2 \vert \gcd(s, j)} \mu(d_2) \right) \\ =& \sum_{d_2 \vert s} \mu(d_2) \sum_{d_1 = 1} ^ n \left\lfloor \frac{n}{\operatorname{lcm}(d_1, d_2)} \right\rfloor \mu(d_1) \sum_{i \in Q_{d_1}} \operatorname{overlap}(l_i, r_i, l, r) x_i \end{aligned} \]

其中 \(Q_t\) 表示所有 \(t \vert s_i\) 的修改。

令 \(D = \gcd(d_1, d_2)\)，\(d_1 = d_1 \div D\)，\(d_2 = d_2 \div D\)。

\[ \begin{aligned} =& \sum_{D \vert s} \sum_{d_2 \vert \frac{s}{D}} \mu(d_2 \cdot D) \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \mu(d_1 \cdot D) \left\lfloor \frac{n}{d_1 \cdot d_2 \cdot D} \right\rfloor [\gcd(d_1, d_2) = 1] \sum_{i \in Q_{d_1 \cdot D}} \operatorname{overlap}(l_i, r_i, l, r) x_i \\ =& \sum_{D \vert s} \sum_{d_2 \vert \frac{s}{D}} \mu(d_2 \cdot D) \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \mu(d_1 \cdot D) \left\lfloor \frac{n}{d_1 \cdot d_2 \cdot D} \right\rfloor \sum_{d \vert \gcd(d_1, d_2)} \mu(d) \sum_{i \in Q_{d_1 \cdot D}} \operatorname{overlap}(l_i, r_i, l, r) x_i \\ & \text{令 } D = D \times d \\ =& \sum_{D \vert s} \sum_{d \vert D} \mu(d) \sum_{d_2 \vert \frac{s}{D}} \mu(d_2 \cdot D) \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \mu(d_1 \cdot D) \left\lfloor \frac{n}{d_1 \cdot d_2 \cdot d \cdot D} \right\rfloor \sum_{i \in Q_{d_1 \cdot D}} \operatorname{overlap}(l_i, r_i, l, r) x_i \end{aligned} \]

考虑如何用数据结构来维护这东西。

最外层枚举 \(D\)，\(Q_t\) 为 \(s_i\) 为 \(t\) 倍数的修改集合，\(A_t\) 为 \(s_i\) 为 \(t\) 倍数的询问集合。

一次处理 \(Q_D\) 对 \(A_D\) 的贡献。

对于修改：枚举 \(\sum_{d \vert D}\)，\(\sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor}\)，把区间如 \([l_i, r_i]\) 加 \(x_i\) 记录在第 \(\left\lfloor \frac{n}{d_1 \cdot D \cdot d} \right\rfloor\)（只有 \(\mathcal{O}\left(\sqrt{\frac{n}{D}}\right)\) 种取值）行。

复杂度：

\[ \begin{aligned} & \sum_{D = 1} ^ n \sum_{d \vert D} \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \lvert Q_{D \cdot d_1} \rvert \\ =& \sum_{D = 1} ^ n \sum_{d \vert D} \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \frac{n}{D \cdot d_1} \\ =& \sum_{D = 1} ^ n \sum_{d \vert D} \frac{n}{D} \log n \\ =& \sum_{d = 1} ^ n \sum_{D = 1} ^ {\lfloor \frac{n}{D} \rfloor} \frac{n}{D \cdot d} \log n \\ =& \sum_{d = 1} ^ n \frac{n}{d} \log^2 n \\ =& n \log^3 n \end{aligned} \]

预处理：修改中在一个 \(\mathcal{O}\left( \sqrt{\frac{n}{D}} \right)\) 行，\(n\) 列数组中进行了区间加。

1. 只有 \(\lvert Q_D \rvert + \lvert A_D \rvert\) 行有用，先离散化。
2. 作二维前缀和。

复杂度：

\[ \begin{aligned} & \sum_{D = 1}^n \sqrt{\frac{n}{D}} \left( \lvert Q_D \rvert + \lvert A_D \rvert \right) \\ =& \sum_{D = 1}^n \left( \frac{n}{D} \right)^{1.5} \\ \approx& \int_1^n \left( \frac{n}{x} \right)^{1.5} \text{d}x \\ =& \mathcal{O}(n \sqrt n) \end{aligned} \]

离散化：

\[ \begin{aligned} & \sum_{D = 1}^n \left( \lvert Q_D \rvert + \lvert A_D \rvert \right) \log n \\ =& \sum_{D = 1}^n \left\lfloor \frac{n}{D} \right\rfloor \log n \\ =& n \log^2 n \end{aligned} \]

询问：枚举 \(d_1\)，那么第 \(i\) 行的贡献为 \(\left\lfloor \frac{i}{d_1} \right\rfloor\) 倍。（备注：此处疑似吉老师笔误，这里的 \(d_1\) 实际上枚举的是上面的式子中的 \(d_2\)。包括下几段在内的所有 \(d_1, d_2\) 似乎都应当反过来。）

枚举 \(\left\lfloor \frac{i}{d_1} \right\rfloor\)，注意 \(i = \left\lfloor \frac{n}{d_2 \cdot D \cdot d} \right\rfloor\)，\(\therefore \left\lfloor \frac{i}{d_1} \right\rfloor\) 有 \(\displaystyle \left\lfloor \dfrac{\left\lfloor \frac{n}{D \cdot d_1} \right\rfloor}{x} \right\rfloor\) 的形式，\(\therefore\) 有 \(\displaystyle \mathcal{O}\left( \sqrt{\frac{n}{D \cdot d_1}} \right)\) 段。

每一段是一个矩形和，预处理后 \(\mathcal{O}(1)\)，复杂度：

\[ \begin{aligned} & \sum_{D = 1}^n \sum_{d_1 = 1}^{\lfloor \frac{n}{D} \rfloor} \lvert A_{d_1 \cdot D} \rvert \cdot \sqrt{\frac{n}{d_1 \cdot D}} \\ =& \sum_{D = 1}^n \sum_{d_1 = 1}^{\lfloor \frac{n}{D} \rfloor} \left( \frac{n}{d_1 \cdot D} \right)^{1.5} \\ \approx& \int_1^n \int_1^{\frac{n}{x}} \left( \frac{n}{xy} \right)^{1.5} \text{d}y \text{d}x \\ =& \mathcal{O}(n \sqrt n) \end{aligned} \]

总的时间复杂度为 \(\mathcal{O}(n \log^3 n + n ^ {1.5})\)。

推导部分是非常基础的莫比乌斯反演。

难点在于如何处理 \(n / \operatorname{lcm}\) 这个式子还有复杂度计算。

在我实现过程中，遇到了一些细节，与大家分享一下。

归纳地来说，首先经过一系列的推导可以得到这个式子：

\[ \sum_{D \vert s} \sum_{d_2 \vert \frac{s}{D}} \mu(d_2 \cdot D) \sum_{d \vert D} \mu(d) \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \mu(d_1 \cdot D) \left\lfloor \frac{n}{d_1 \cdot d_2 \cdot d \cdot D} \right\rfloor \sum_{i \in Q_{d_1 \cdot D}} \operatorname{overlap}(l_i, r_i, l, r) x_i \]

然后我们用数据结构去维护它。

注意到一个询问 \(s, l, r\)，这三个变量在这个式子中出现的地方只有：前面枚举 \(D, d_2\) 的时候出现了 \(s\)，最后求交集的时候出现了 \(l, r\)。这里的 \(l, r\) 显然可以二维差分+二维前缀和在每次询问时再查询，因此可以先放着不管。

在我们最外层枚举 \(D\) 了以后，会被影响到的询问就是那些 \(D\) 的倍数的询问。我们交换求和号，枚举询问，式子变成

\[ \sum_{D = 1} ^ n \sum_{d \vert D} \mu(d) \sum_{d_1 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \mu(d_1 \cdot D) \sum_{d_2 = 1} ^ {\lfloor \frac{n}{D} \rfloor} \mu(d_2 \cdot D) \left\lfloor\frac{\left\lfloor \frac{n}{d_1 \cdot d \cdot D} \right\rfloor}{d_2} \right\rfloor \sum_{i \in Q_{d_1 \cdot D}} \sum_{D \cdot d_2 \vert j} \operatorname{overlap}(l_i, r_i, l_j, r_j) x_i \Rightarrow Ans_j \]

后面 \(\Rightarrow Ans_j\) 表示给 \(Ans_j\) 的值加上这么多。

对于每个修改，我们枚举 \(D, d, d_1\)，在 \(\displaystyle \left\lfloor \frac{n}{d_1 \cdot d \cdot D} \right\rfloor\) 行打上标记。在查询时枚举 \(d_2\)，然后对于第 \(i\) 行，它对这个查询贡献的系数自然就是 \(\lfloor \frac{i}{d_2} \rfloor\)。

在最后查询枚举 \(\lfloor \frac{i}{d_2} \rfloor\) 时，我们将式子还原成

\[ \left\lfloor\frac{\left\lfloor \frac{n}{d_1 \cdot d \cdot D} \right\rfloor}{d_2} \right\rfloor \]

然后交换 \(d_1, d_2\)，就可以通过知道一段连续的 \(d_1\)，对应的 \(\frac{i}{d_2}\) 的值是相同的，再用 \(d_1\) 的取值区间，根据 \(i = \displaystyle \left\lfloor \frac{n}{d_1 \cdot d \cdot D} \right\rfloor\) 还原出 \(i\) 的取值区间，查一个二维矩形和就可以了。

最后贴上我的丑陋代码。在本校 OJ 上测极限数据是 3.5s，应该是还有卡常的空间吧。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

const int MaxN = 50000 + 5, MaxM = 50000 + 5;
const int MaxQ1 = 50000 + 5, MaxQ2 = 100000 + 5;

struct data {
  int l, r;
  data(int _l = 0, int _r = 0) { l = _l, r = _r; }
  inline friend bool operator < (const data &x, const data &y) { return x.l != y.l ? x.l < y.l : x.r < y.r; }
  inline friend bool operator == (const data &x, const data &y) { return x.l == y.l && x.r == y.r; }
};

int N, M, Q1, Q2;
int Qs[MaxQ1], Ql[MaxQ1], Qr[MaxQ1]; unsigned Qx[MaxQ1];
int As[MaxQ2], Al[MaxQ2], Ar[MaxQ2]; unsigned Ans[MaxQ2];
bool NotPrime[MaxN];
int Prs[MaxN], Prc; unsigned Mu[MaxN];
std::vector<int> Factor[MaxN];
std::vector<int> Q[MaxN], A[MaxN];

void init() {
  scanf("%d %d %d %d", &N, &M, &Q1, &Q2);
  for (int i = 1; i <= Q1; ++i)
    scanf("%d %d %d %u", &Qs[i], &Ql[i], &Qr[i], &Qx[i]);
  for (int i = 1; i <= Q2; ++i)
    scanf("%d %d %d", &As[i], &Al[i], &Ar[i]);
  for (int i = 1; i <= N; ++i)
    for (int j = 1; i * j <= N; ++j)
      Factor[i * j].push_back(i);
  for (int i = 1; i <= Q1; ++i)
    for (int v : Factor[Qs[i]]) Q[v].push_back(i);
  for (int i = 1; i <= Q2; ++i)
    for (int v : Factor[As[i]]) A[v].push_back(i);
  NotPrime[1] = true;
  Mu[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (NotPrime[i] == false) {
      Prs[++Prc] = i;
      Mu[i] = (unsigned) -1;
    }
    for (int j = 1; j <= Prc; ++j) {
      int k = i * Prs[j];
      if (k > N) break;
      NotPrime[k] = true;
      if (i % Prs[j] == 0) break;
      Mu[k] = -Mu[i];
    }
  }
}

void solve() {
  for (int D = 1; D <= N; ++D) {
    std::vector<int> line;
    std::vector<data> column;
    std::vector< std::vector<unsigned> > a;
    line.clear(); column.clear(); a.clear();
    for (int l = 1, r = 0; l <= N / D; l = r + 1) {
      r = (N / D) / (N / D / l);
      line.push_back(N / D / l);
    }
    std::sort(line.begin(), line.end());
    for (int q : Q[D]) {
      column.push_back(data(Ql[q], Ql[q]));
      column.push_back(data(Qr[q], Qr[q]));
    }
    for (int q : A[D]) {
      column.push_back(data(Al[q], Al[q]));
      column.push_back(data(Ar[q], Ar[q]));
    }
    std::sort(column.begin(), column.end());
    int n = (int) line.size(), m = std::unique(column.begin(), column.end()) - column.begin();
    column.erase(column.begin() + m, column.end());

    int hbr = 0;
    std::vector<data> lostRange;
    lostRange.clear();
    for (data p : column) {
      if (hbr + 1 <= p.l - 1) lostRange.push_back(data(hbr + 1, p.l - 1));
      hbr = p.r;
    }
    if (hbr < N) lostRange.push_back(data(hbr + 1, N));
    for (data p : lostRange) {
      column.push_back(p);
      m++;
    }
    std::sort(column.begin(), column.end());

    a.resize(n);
    for (int i = 0; i < n; ++i) a[i].resize(m + 1);

    static int lnkLine[MaxN], lnkColumn[MaxM];
    for (int i = 0; i < n; ++i) lnkLine[line[i]] = i;
    for (int i = 0; i < m; ++i)
      if (column[i].l == column[i].r)
        lnkColumn[column[i].l] = i;

    // printf("D = %d, n = %d, m = %d\n", D, n, m);
    // for (int i = 0; i < n; ++i)
    //   printf("%d%c", line[i], " \n"[i == n - 1]);
    // for (int i = 0; i < m; ++i)
    //   printf("(%d, %d)%c", column[i].l, column[i].r, " \n"[i == m - 1]);

    for (int d : Factor[D]) {
      // printf("d = %d\n", d);
      for (int d1 = 1; d1 <= N / (D * d); ++d1) {
        // printf("d1 = %d\n", d1);
        for (int q : Q[d1 * D]) {
          // printf("q = %d\n", q);
          unsigned k = Mu[d] * Mu[d1 * D] * Qx[q];
          int targetLine = lnkLine[N / (d1 * d * D)];
          int lnkl = lnkColumn[Ql[q]], lnkr = lnkColumn[Qr[q]];
          a[targetLine][lnkl] += k; a[targetLine][lnkr + 1] -= k;
        }
      }
    }

    auto qpos = [&](int x, int y) {
      if (x < 0 || y < 0) return 0u;
      else return a[x][y];
    };

    auto qrect = [&](int x1, int y1, int x2, int y2) {
      return qpos(x2, y2) - qpos(x1 - 1, y2) - qpos(x2, y1 - 1) + qpos(x1 - 1, y1 - 1);
    };

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        a[i][j] += qpos(i, j - 1);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        a[i][j] *= (column[j].r - column[j].l + 1);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        a[i][j] += qpos(i, j - 1) + qpos(i - 1, j) - qpos(i - 1, j - 1);

    for (int d2 = 1; d2 <= N / D; ++d2)
      for (int l = 1, r = 0; l <= N / (D * d2); l = r + 1) {
        r = N / (D * d2) / (N / (D * d2) / l);
        unsigned k = Mu[D * d2] * (N / (D * d2) / l);
        if (k == 0) continue;
        for (int q : A[D * d2])
          Ans[q] += k * qrect(lnkLine[N / D / r], lnkColumn[Al[q]], lnkLine[N / D / l], lnkColumn[Ar[q]]);
      }
  }
  for (int q = 1; q <= Q2; ++q) printf("%u\n", Ans[q]);
}

int main() {
  init();
  solve();
  return 0;
}

原文地址：https://www.cnblogs.com/tweetuzki/p/12159912.html