题解：P8283 「MCOI-08」Dantalion

w33z8kqrqk8zzzx33 · 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;
}