CF2179H | Ficon's Paper

这道题挺难的。

感觉不止 2200，实现方面有很多细节需要注意。

x = 31 - __builtin_clz(n) 表示的是 n 的最高位，比如 n = 5, x = 2

有 $n$ 个植物， $q$ 次操作，每次选取一个 $l, r$ ，为每一个 $i \in [l, r]$ 的植物都浇 $f(i - l + 1)$ 个单位的水，其中 $f(x) = x \times lowbit(x)$

先考虑简化版： $f(x) = lowbit(x)$

假设 $lowbit(x) = 2^k$ ，二进制拆分： $2^k=2^{k-1}+2^{k-2}+\dots+2^1+2^0+1$

给一个 $i$ 加 $2^k$ 单位的水，可以拆分成加这么多次的水。 $2^k$ 整除 $x=i-l+1$ ，那么拆分的每一项都整除 $x$ ，也就是说，只要 $x$ 整除 $2^a$ ，就为其加上 $2^{a-1}$ 单位个水，最后每个位置都要加上单独的一个 1。

$i-l+1\equiv 0 \pmod{2^a}$

即 $i\equiv l-1 \pmod{2^a}$

也就是说，我们要为每一个满足 $i\equiv l-1 \pmod{2^a}$ 的位置加上 $2^{a-1}$ ，两个位置之间间隔为 $2^{a-1}$ ，可以采用分层差分来处理，找到区间内第一个满足条件的位置和最后一个满足条件的位置，同除 $2^a$ 作为数组中的下标映射：比如在模 2 的情况下，1 3 5 7 9 对应数组下标 0 1 2 3 4。

可以用 [模数][余数][系数] 的方式实现：diff[1][1][0] 代表的就是 $2^1\times 0 + 1$ ，也可以合并后面两维，根据步长来进行分层差分数组的划分，具体参考下面的两种实现代码。

简单的版本考虑完了，来考虑一下复杂的版本， $f(x)=x\times lowbit(x)$ ，多了一个系数 $x=i - l + 1$ ，对于每次的修改，从原来的 $2^{a-1}$ 变成了 $2^{a-1}\times(i - l + 1)$ ，可以拆成： $2^{a-1}\times i - 2^{a-1} \times (l-1)$ ，第二项是一个常数，正常差分修改，第一项有系数，需要单独开一个差分数组来记录。

需要注意的是，由于是多测，每次枚举范围和初始化的范围不要超过 $n$ ，因为题目数据只保证 $\sum{n}\le{2e{5}}$ ，具体实现细节看代码。

在 [模数][余数][系数] 的实现里，设系数为 $k$ ，那么 $i=k\times 2^{a} + j$ ，可以把 $j$ 这个余数也提取出去，这样常量差分数组每次修改其实就是加上 $j-(l-1)$ ，系数差分数组每次维护的是 $2^a\times 2^{a-1}$ 。

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;

void solve() {
  int n, q;
  cin >> n >> q;
  int sz = 31 - __builtin_clz(n);
  vi d(n + 2);
  ve<ve<ve<ll>>> diff0(20), diff1(20);
  for (int i = 0; i <= sz; i++) {
    diff0[i].assign(1 << i, ve<ll>(n / (1 << i) + 2));
    diff1[i].assign(1 << i, ve<ll>(n / (1 << i) + 2));
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    int sz = 31 - __builtin_clz(r - l + 1);
    for (int i = 0; i <= sz; i++) {
      int mod = (1 << i);
      int val = i == 0 ? 1 : (1 << (i - 1));
      int rem = (l - 1) % mod;
      int L = l + (rem - l % mod + mod) % mod;
      int R = r - (r % mod - rem + mod) % mod;
      diff0[i][rem][L / mod] += 1ll * (rem - l + 1) * val;
      diff0[i][rem][R / mod + 1] -= 1ll * (rem - l + 1) * val;
      diff1[i][rem][L / mod] += 1ll * mod * val;
      diff1[i][rem][R / mod + 1] -= 1ll * mod * val;
    }
  }
  ve<ll> ans(n + 1);
  for (int i = 0; i <= sz; i++) {
    for (int j = 0; j < (1 << i); j++) {
      ll sum0 = 0;
      ll sum1 = 0;
      for (int k = 0; k <= n / (1 << i); k++) {
        int x = (1 << i) * k + j;
        if (x > n)
          break;
        sum0 += diff0[i][j][k];
        sum1 += diff1[i][j][k];
        ans[x] += sum0 + sum1 * k;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}

不展开公式的版本：

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;

void solve() {
  int n, q;
  cin >> n >> q;
  int sz = 31 - __builtin_clz(n);
  vi d(n + 2);
  ve<ve<ve<ll>>> diff0(20), diff1(20);
  for (int i = 0; i <= sz; i++) {
    diff0[i].assign(1 << i, ve<ll>(n / (1 << i) + 2));
    diff1[i].assign(1 << i, ve<ll>(n / (1 << i) + 2));
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    int sz = 31 - __builtin_clz(r - l + 1);
    for (int i = 0; i <= sz; i++) {
      int mod = (1 << i);
      int val = i == 0 ? 1 : (1 << (i - 1));
      int rem = (l - 1) % mod;
      int L = l + (rem - l % mod + mod) % mod;
      int R = r - (r % mod - rem + mod) % mod;
      diff0[i][rem][L / mod] -= 1ll * (l - 1) * val;
      diff0[i][rem][R / mod + 1] += 1ll * (l - 1) * val;
      diff1[i][rem][L / mod] += 1ll * val;
      diff1[i][rem][R / mod + 1] -= 1ll * val;
    }
  }
  ve<ll> ans(n + 1);
  for (int i = 0; i <= sz; i++) {
    for (int j = 0; j < (1 << i); j++) {
      ll sum0 = 0;
      ll sum1 = 0;
      for (int k = 0; k <= n / (1 << i); k++) {
        int x = (1 << i) * k + j;
        if (x > n)
          break;
        sum0 += diff0[i][j][k];
        sum1 += diff1[i][j][k];
        ans[x] += sum0 + sum1 * x;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}

步长分层差分的版本：

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;
const int N = 2e5 + 7;

ll diff0[20][N], diff1[20][N];

void solve() {
  int n, q;
  cin >> n >> q;
  int sz = 31 - __builtin_clz(n);
  for (int i = 0; i <= sz; i++) {
    for (int j = 1; j <= n; j++) {
      diff0[i][j] = 0;
      diff1[i][j] = 0;
    }
  }
  vi d(n + 2);
  while (q--) {
    int l, r;
    cin >> l >> r;
    int sz = 31 - __builtin_clz(r - l + 1);
    for (int i = 0; i <= sz; i++) { // tag
      int k = ((r - l + 1) >> i);
      int L = l + (1 << i) - 1;
      if (L > r)
        break;
      int R = min(n + 1, l + ((k + 1) << i) - 1);
      diff0[i][L]++;
      diff0[i][R]--;
      diff1[i][L] -= (l - 1);
      diff1[i][R] += (l - 1);
    }
  }
  ve<ll> ans(n + 1);
  for (int i = 0; i <= sz; i++) {
    for (int j = 1; j <= n; j++) {
      if (j > (1 << i)) {
        diff0[i][j] += diff0[i][j - (1 << i)];
        diff1[i][j] += diff1[i][j - (1 << i)];
      }
      ll val = (1 << max(0, i - 1));
      ans[j] += diff0[i][j] * j * val + diff1[i][j] * val;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}