CWOI S C0369 C follow

題意

U2FsdGVkX1+ou6s6crFQdww8deCQBJrYgRMpAgTUPcZKoLkL+0fFmVsVcpolZ3aW
QoC+Q5rO+BLIWWP2n18pH+tCz+zUyE1RJ965ySjCLDL6y7t7DS3iCyP0b51LOclM
eROIZQoF4nA49INckOzAxGVNsNroeR7mrX906KoNMdr8yrZH74//8jcZBew0jy8t
zpjKQqTJ8nxB7W4dxjj18WUkwJN+d5hWMsMZrDzAl+Q=

解析

考慮單次詢問如何處理。首先，通過雙指標預處理 next(i) 表示出每個端點，向後最多延伸多少距離，能滿足條件，這個過程是 $O(n)$ 的。對於任意一個 i，從 i + 1 到 i + next(i) 必然有一個位置是最優解某一段的端點，同時，容易知道 $next(i) \ge k$ 所以找到最小的 next(i)，列舉 i + 1 到 i + next(i)，然後暴力跳 next，這樣的複雜度是 $O(\frac{k} \times \frac{n}{k}) = O(n)$ 的。

然後考慮處理多次詢問。對於 k > n，顯然答案為 1。然後可以考慮根號分治。對於 k <= B，直接用上面的過程預處理。對於 k > B，這時答案一定小於 $\frac{n}{B}$，不會太大，所以列舉答案，二分找答案對應的 k 的範圍。複雜度 $O(nB + \frac{n}{B}\times n \log n)$。當 $B = \sqrt{n\log n}$ 時，可以做到 $O(n\sqrt{n\log n})$。

比較卡常數。對於環狀的陣列，需要對下標取模，然而對於這道題下標不會太大，可以用多次減法代替取模，最佳化極大。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <optional>
#include <string>
#include <vector>

#include <ctime>

template <typename T>
struct circular_vector
{
  std::vector<T> a;

  circular_vector(int n) : a(n) {}

  auto begin() { return a.begin(); }
  auto end() { return a.end(); }
  auto size() const { return a.size(); }

  auto calc_index(size_t x) const
  {
    auto s = size();
    while (x >= s) x -= s;
    return x;
  }
  auto operator[](size_t x) const { return a[calc_index(x)]; }
  auto &operator[](size_t x) { return a[calc_index(x)]; }
};

int main()
{
  int n, m;
  std::cin >> n >> m;

  circular_vector<int> a(n);
  std::vector<int> cc;
  for (auto &i : a) {
    std::cin >> i;
    cc.emplace_back(i);
  }
  std::sort(cc.begin(), cc.end());
  cc.erase(std::unique(cc.begin(), cc.end()), cc.end());
  for (auto &i : a) i = std::lower_bound(cc.begin(), cc.end(), i) - cc.begin();

  int max_val = cc.size();

  std::vector<std::optional<int>> f(n + 1);

  auto solve = [&a, n, &f, max_val](int k)
  {
    if (f[k]) return *f[k];

    circular_vector<int> next(n);
    std::vector<int> cnt(max_val);
    int j = 0;
    for (int i = 0; i < n; i++) {
      while (j - i < n && cnt[a[j]] + 1 <= k) {
        cnt[a[j]]++;
        j++;
      }
      next[i] = j - i;
      cnt[a[i]]--;
    }

    int min_seg = std::min_element(next.begin(), next.end()) - next.begin();

    int ans = n;
    for (int i = 1; i <= next[min_seg]; i++) {
      int cnt = 0;
      int p = i + min_seg;
      int q = p;
      while (q - p < n) {
        q += next[q];
        cnt++;
      }
      ans = std::min(ans, cnt);
    }

    f[k] = ans;

    return ans;
  };

  if (m == 1) {
    int k;
    std::cin >> k;
    std::cout << solve(k) << std::endl;
    return 0;
  }

  int B = std::min(n, (int)std::sqrt(n * std::log(n)));

  for (int i = 1; i <= B; i++) solve(i);

  {
    int last = B + 1;
    for (int i = *f[B]; i >= 1 && last <= n; i--) {
      if (solve(last) < i) continue;
      int l = last, r = n + 1;
      while (l < r) {
        int mid = l + (r - l) / 2;
        if (solve(mid) < i) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      for (int j = last; j < r; j++) {
        f[j] = i;
      }
      last = r;
    }
  }

  for (int i = 0; i < m; i++) {
    int k;
    std::cin >> k;
    if (k > n) std::cout << 1;
    else std::cout << *f[k];
    std::cout << std::endl;
  }
}