[ds 记录] P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

首 Ynoi。

这题用 CF765F 那个方法能做但是肯定慢得飞起（\(n \sqrt{n}\) 个 long long）。这个方法挺依赖逆序对性质，比如可减性，以及方便通过值域上的前缀和求贡献。

算法流程：

1. 处理出 \(pre_i\) 和 \(nxt_i\)，分别表示 \(i\) 到块头块尾的散块的答案。暴力即可，\(O(n \log n)\)，多的 \(\log\) 是树状数组，反正不是瓶颈。
2. 处理出 \(ans_{i,j}\) 表示第 \(i\) 到第 \(j\) 个块的答案。这里需要算块对块的贡献，但是不用精细到具体点。
3. 处理出方便单点对单块算答案的信息。当然可以直接对每个块列出值域分布后前缀和，直接处理每个点到每个块后前缀和也行。

上一个算法直接处理了单点到块边界的答案来直接处理散块对整块的贡献，挺通用。而这个算法需要快速算单单点对一个前缀块的贡献。常数会大一些，空间小一点。但这道题的空间也是 \(n \sqrt{n}\)，因为对块的值域后缀和做了块维度的前缀和。所以感觉两个差不多？但是这个就是选择少预处理了一点东西，用 cnt 数组换取 \(pre\) 和 \(nxt\) 数组只用开到线性。

思路还是一致的：

• 散块对散块（能排序就能 \(O(\sqrt{n})\)）
• 整块对散块（预处理、前缀和）
• 整块对整块（预处理，前缀和时要算块对块贡献）

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 1e5 + 5, N = 725;
int n, m, a[M], len, block, L[N], R[N], pos[M], pre[M], nxt[M];
// nxt / pre ：到该数所属块尾 / 块头的贡献
// ans[i][j] ： i 块到 j 块的贡献
pair<int, int> b[M];
LL ans[N][N];
int cnt[N][M], s[M];
// cnt[i][j] : 前 i 块中 >= j 的数的个数
inline void add(int x) {
  for (int i = x; i <= n; i += i & (-i)) ++s[i];
}
inline void del(int x) {
  for (int i = x; i <= n; i += i & (-i)) --s[i];
}
inline int query(int x) {
  int res = 0;
  for (int i = x; i; i -= i & (-i)) res += s[i];
  return res;
}
int calc(int x, int y, int l1, int r1, int l2, int r2) {
  int pos = L[y] - 1, tot = 0, res = 0;
  for (int i = L[x]; i <= R[x]; ++i) {
    if(l1 <= b[i].second && b[i].second <= r1) {
      while (pos < R[y] && b[i].first > b[pos + 1].first) {
        ++pos; if(l2 <= b[pos].second && b[pos].second <= r2) ++tot;
      }
      res += tot;
    }
  }
  return res;
}
void init() {
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = {a[i], i};
  len = sqrt(n) / 2; block = (n - 1) / len + 1;
  for (int i = 1; i <= block; ++i) L[i] = R[i - 1] + 1, R[i] = i * len;
  R[block] = n;
  for (int i = 1; i <= block; ++i) {
    int x = 0;
    for (int j = L[i]; j <= R[i]; ++j) {
      pos[j] = i, ++cnt[i][a[j]];
      x += j - L[i] - query(a[j]), pre[j] = x, add(a[j]);
    }
    ans[i][i] = x;
    for (int j = L[i]; j <= R[i]; ++j) {
      nxt[j] = x, del(a[j]), x -= query(a[j]);
    }
    int res = 0;
    for(int j = 1; j <= n; j++)
      res += cnt[i][j], cnt[i][j] = res + cnt[i - 1][j];
    sort(b + L[i], b + R[i] + 1);
  }
  for(int l = 2; l <= block; ++l) {
    for(int i = 1; i + l - 1 <= block; ++i) {
      int j = i + l - 1;
      ans[i][j] = ans[i + 1][j] + ans[i][j - 1] - ans[i + 1][j - 1] + calc(i, j, L[i], R[i], L[j], R[j]);
    }
  }
}

LL query(int l, int r) {
  int p = pos[l], q = pos[r]; LL res = 0;
  if (p == q) {
    if(l == L[p]) return pre[r];
    return pre[r] - pre[l - 1] - calc(p, p, 1, l - 1, l, r);
  }
  res = nxt[l] + pre[r] + calc(p, q, l, R[p], L[q], r) + ans[p + 1][q - 1];
  for (int i = l; i <= R[p]; ++i) res += cnt[q - 1][a[i]] - cnt[p][a[i]];
  for (int i = L[q]; i <= r; ++i)
    res += R[q - 1] - L[p + 1] + 1 - cnt[q - 1][a[i]] + cnt[p][a[i]];
  return res;
}

LL last;
void solve() {
  while (m--) {
    int l, r; scanf("%d %d", &l, &r);
    l ^= last; r ^= last;
    printf("%lld\n", last = query(l, r));
  }
}
int main() {
  init(); solve();
}