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