自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:37:38，当前版本为作者最后更新于2025-01-10 15:19:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

通过一系列转换问题变成：对于 $n<2^{21}$ 以及一个形如 $S=\{[A_i,B_i]\times i\}$ 的点集，如何用 $16n+o(\dots)$ 字节预处理出 $O(1)$ 统计 $S\cap[L,R]^2$。

而 $S$ 是一个差 $S_1-S_2$，$S_1=\{[1,B_i]\times i\}$, $S_2=\{[1,A_i-1]\times i\}$。对于 $S_1$ 可以算出 $B_i$ 前缀和以及 $h_L=\min \{i:B_i\ge L\}$ 得到 $S_1\cap[L,R]^2=\{[L,B_i]\times i,i\in[h_L,R]\}$ 的大小，$S_2$ 同理。

因为 $\max h\times \max\sum B<2^{64}$ 可以把所有信息压到一个 ulong 里面，每一个集合使用 $8n$ 字节预处理，总共使用 $16n$ 字节。

long long solve(int l, int r) {
  long long c = 1ll * LOGN * (r - l + 1);
  if (l) {
    for (int b = 0; b < LOGN; b++) {
      int bo;
      bo = max(l, min(r + 1, (int)(maxL[l - 1][b]&1048575)));
      c += (maxL[r][b]>>20) - (maxL[bo - 1][b]>>20) + 1ll * (l - 1) * (bo - l);
      bo = max(l, min(r + 1, (int)(minL[l][b]&1048575)));
      c -= (minL[r][b]>>20) - (minL[bo - 1][b]>>20) + 1ll * l * (bo - l);
    }
  } else {
    for (int b = 0; b < LOGN; b++)
      c += (maxL[r][b]>>20) - (minL[r][b]>>20);
  }
  return c;
}