⭐例题 Genius_ACM

考虑到二分会有很多低效的操作（如：二分第一步检验 0x06 倍增 - 图1 这么长一段但右端点只会移动很少的部分），直接换倍增写。

  1. 初始化 0x06 倍增 - 图2
  2. 求出 0x06 倍增 - 图3 区间的“检验值” ,若 检验值 0x06 倍增 - 图4 则 0x06 倍增 - 图5 ，否则 0x06 倍增 - 图6
  3. 重复上一步直到 0x06 倍增 - 图7 ，此时 R 为所求值
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll    = long long;
  4. const int N = 500006;
  5. int n, m, w;
  6. ll k, a[N], b[N], c[N];
  8. void gb(int l, int mid, int r) {
  9.     int i = l, j = mid + 1;
  10.     for (int k = l; k <= r; k++)
  11.         if (j > r || (i <= mid && b[i] <= b[j])) c[k] = b[i++];
  12.         else
  13.             c[k] = b[j++];
  14. }
  16. ll f(int l, int r) {
  17.     if (r > n) r = n;
  18.     int t = min(m, (r - l + 1) >> 1);
  19.     for (int i = w + 1; i <= r; i++) b[i] = a[i];
  20.     sort(b + w + 1, b + r + 1);
  21.     gb(l, w, r);
  22.     ll ans = 0;
  23.     for (int i = 0; i < t; i++)
  24.         ans += (c[r - i] - c[l + i]) * (c[r - i] - c[l + i]);
  25.     return ans;
  26. }
  28. void Genius_ACM() {
  29.     cin >> n >> m;
  30.     cin >> k;
  31.     for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  32.     int ans = 0, l = 1, r = 1;
  33.     w    = 1;
  34.     b[1] = a[1];
  35.     while (l <= n) {
  36.         int p = 1;
  37.         while (p) {
  38.             ll num = f(l, r + p);
  39.             if (num <= k) {
  40.                 w = r = min(r + p, n);
  41.                 for (int i = l; i <= r; i++) b[i] = c[i];
  42.                 if (r == n) break;
  43.                 p <<= 1;
  44.             } else
  45.                 p >>= 1;
  46.         }
  47.         ans++;
  48.         l = r + 1;
  49.     }
  50.     cout << ans << endl;
  51. }
  53. int main() {
  54.     int t;
  55.     cin >> t;
  56.     while (t--) Genius_ACM();
  57.     return 0;
  58. }