题解：QOJ14949 The Echoes of Chronos

题解：QOJ14949 The Echoes of Chronos

题目描述

一次外出，小 Z 发现了月灯。月灯的本体是一个长度为 \(n\) 的序列 \(A=[a_1,a_2,\cdots,a_n]\)。初始，每个元素都是 \(0\) 至 \(m-1\) 间的整数。

一次修改操作，小 Z 会选择一个整数 \(x\) 满足 \(0\leq x<m\)，并执行以下操作之一恰好一次：

• 将序列中的所有 \(x\) 同时变成 \((x+1)\bmod m\)。
• 将序列中的所有 \(x\) 同时变成 \((x-1)\bmod m\)。

小 Z 发现月灯的亮度只与序列 \(A\) 中一段区间的最大值和最小值有关，于是他会问你 \(q\) 个问题：每次给定 \(l,r,v\)，你需要求出使得 \(\min⁡(a_l,a_{l+1},\cdots ,a_r)=\max⁡(a_l,a_{l+1},\cdots,a_r)=v\) 的最少修改操作次数。小 Z 可以进行任意多次修改操作，也可以不进行任何修改。

\(n, q\leq 200000\)，\(a_i,v<m\leq 10^9\)。

题解

做法：假设没有 \(v\)，也就是询问是查询 \(S=\{a_x|l\leq x\leq r\}\) 这个当作环的集合的邻项差的最大值，可以回滚莫队，即维护一个链表进行不断删除，删除过程中答案只会增加，所以可以做到 \(O(n\sqrt m)\)。原来询问中的 \(v\) 的影响，就是往 \(S\) 里面加入 \(v\) 再算答案，这对我们用链表的算法有毁灭性的打击。所以考虑将询问按照左端点排序后按照一定规则分块，块内的询问一起做回滚莫队，初始化链表时除了加入 \(a\) 中的数还加入所有询问的 \(v\)，处理每个询问的时候直接删除其它询问的 \(v\)。假设 \(n, q\) 同阶，我们保证每个块满足询问数量不超过 \(O(\sqrt n)\)，而且询问左端点的极差不超过 \(O(\sqrt n)\)，这样单次回滚莫队的复杂度就不超过 \(O(n)\)。贪心分块，按照左端点顺序将询问加入块，直到一个块不满足以上条件时就做回滚莫队，这样回滚莫队的次数也不超过 \(O(n\sqrt n)\)，总复杂度不超过 \(O(n\sqrt n)\)。常数较大，但也能通过。

假设询问中没有参数 \(v\)，即仅需要查询集合 \(S = \{a_x \mid l \le x \le r\}\)（视作环形序列）中相邻两项差的最大值。这一问题可以通过回滚莫队算法解决：使用链表结构维护集合，并在不断删除元素的过程中更新答案。由于删除操作只会使答案增大，因此可以在 \(O(n\sqrt{m})\) 的时间复杂度内完成。

在原问题中，询问包含参数 \(v\)，其作用相当于先将 \(v\) 加入集合 \(S\)，再计算答案。这给上述基于链表的算法带来了较大困难。为此，我们考虑对询问进行分块处理：首先按左端点 \(l\) 排序，然后依据一定规则将询问分块，在每个块内统一执行回滚莫队（只需要初始化一次，不需要再分块）。初始化链表时，除了加入序列 \(a\) 中对应位置的元素外，还需加入该块内所有询问的 \(v\) 值。在处理具体某个询问时，只需移除其它询问对应的 \(v\) 值即可。

假设 \(n\) 与询问数 \(q\) 同阶，我们确保每个块满足以下两个条件：

1. 块内询问数量不超过 \(O(\sqrt{n})\)；
2. 块内询问左端点的极差不超过 \(O(\sqrt{n})\)。

在这样的设定下，每次执行回滚莫队的复杂度可控制在 \(O(n)\) 以内。

我们采用贪心策略进行分块：按左端点顺序依次将询问加入当前块，直到违反上述任一条件时，立即对该块执行回滚莫队并开启新块。这样一来，回滚莫队的执行总次数不超过 \(O(\sqrt{n})\) 次，整体时间复杂度为 \(O(n\sqrt{n})\)。

尽管该算法的常数较大，但仍可在合理时间内通过本题。

代码

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
struct flower {
  vector<T> vec;
  flower& operator<<(const T& x) { vec.push_back(x); return *this; }
  int build() {
    auto bg = vec.begin(), ed = vec.end();
    sort(bg, ed), vec.erase(unique(bg, ed), ed);
    return (int)vec.size();
  }
  int operator()(const T& x) const { return lower_bound(vec.begin(), vec.end(), x) - vec.begin(); }
  T operator[](int x) const { return vec[x]; }
};
constexpr int N = 2e5 + 16384, BQ = 512;
struct ask {
  int l, r, v, id;
};
int n, q, mxv, m, a[N], fans[N];
flower<int> hua;
pair<int, int> srt2[N];
inline int cdj(int l, int r) {
//assert(l != r);
  if (l < r) return hua[r] - hua[l] - 1;
  return mxv - (hua[l] - hua[r]) - 1;
}
int bcnt = 0, dcnt = 0;
template <int N>
struct linked_lst {
  int L[N], R[N], ans, cnt[N];
  vector<pair<int&, int>> und;
  void rem(int &x) { und.emplace_back(x, x); }
  void upd(int x) { if (x > ans) ans = x; }
  void build(int vec[], int sz) {
    bcnt += sz;
    for (int i = 0; i < sz; i++) cnt[vec[i]] = 0, debug("%d ", vec[i]); debug("\n");
    int fir = -1, lst = -1;
    ans = -1e9, und.clear();
    for (int i = 0; i < sz; i++) {
      int v = vec[i];
      cnt[v] += 1;
      if (lst == -1) fir = lst = v;
      else if (lst != v) upd(cdj(lst, v)), R[lst] = v, L[v] = lst, lst = v;
    }
    assert(fir != -1);
    upd(lst == fir ? mxv - 1: cdj(lst, fir));
    R[lst] = fir, L[fir] = lst;
  }
  void del(int x) {
    dcnt += 1;
//  rem(cnt[x]);
    if (--cnt[x]) return ;
    rem(R[L[x]]), rem(L[R[x]]);//, rem(ans);
    R[L[x]] = R[x];
    L[R[x]] = L[x];
    upd(L[x] == R[x] ? mxv - 1 : cdj(L[x], R[x]));
  }
  void rollback(size_t tim) {
    while (und.size() > tim) {
      und.back().first = und.back().second;
      und.pop_back();
    }
  }
};
linked_lst<N << 1> lst, lst0; // n + q
int ccnt = 0;
void solveall(vector<ask> qry) {
  ccnt += 1;
  int bl = qry.front().l, br = qry.back().l;
  static int num1[N], cnt1; cnt1 = (int)qry.size();
  for (int i = 0; i < cnt1; i++) num1[i] = qry[i].v;
  sort(num1, num1 + cnt1);
  static int num2[N], cnt2; cnt2 = 0;
  for (int i = 1; i <= n; i++) if (srt2[i].second >= bl) num2[cnt2++] = srt2[i].first;
  static int num3[N << 1], cnt3; cnt3 = cnt1 + cnt2;
  merge(num1, num1 + cnt1, num2, num2 + cnt2, num3);
  lst.build(num3, cnt3);
  sort(qry.begin(), qry.end(), [&](auto lhs, auto rhs) { return lhs.r > rhs.r; });
  int l = bl, r = n;
  static vector<pair<int, int>> srt3; srt3.clear();
  for (int i = bl; i <= br; i++) srt3.push_back({a[i], i});
  sort(srt3.begin(), srt3.end());
  for (auto [ql, qr, v, id] : qry) {
    if (qr <= br) {
      static vector<int> tmp; tmp.clear();
      for (auto [vp, p] : srt3) if (ql <= p && p <= qr) tmp.push_back(vp);
      tmp.insert(upper_bound(tmp.begin(), tmp.end(), v), v);
      lst0.build(tmp.data(), (int)tmp.size());
      fans[id] = lst0.ans;
    } else {
      while (r > qr) lst.del(a[r--]);
      auto tim = lst.und.size();
      lst.rem(l), lst.rem(lst.ans);
      while (l < ql) lst.del(a[l++]);
      assert(l == ql && r == qr);
      bool flag = false;
      for (int i = 0; i < cnt1; i++) {
        int vp = num1[i];
        if (!flag && vp == v) flag = true;
        else lst.del(vp);
      }
      assert(flag);
      fans[id] = lst.ans;
      while (l > bl) lst.cnt[a[--l]] += 1;
      flag = false;
      for (int i = 0; i < cnt1; i++) {
        int vp = num1[i];
        if (!flag && vp == v) flag = true;
        else lst.cnt[vp] += 1;
      }
      lst.rollback(tim);
    }
  }
}
vector<ask> buc[N];
int main() {
#ifndef LOCAL
#ifndef NF
  freopen("moonlamp.in", "r", stdin);
  freopen("moonlamp.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n >> q >> mxv;
  for (int i = 1; i <= n; i++) cin >> a[i], hua << a[i];
  for (int i = 1, l, r, v; i <= q; i++) cin >> l >> r >> v, buc[l].push_back({l, r, v, i}), hua << v;
  m = hua.build();
  for (int i = 1; i <= n; i++) a[i] = hua(a[i]), srt2[i] = {a[i], i};
  sort(srt2 + 1, srt2 + n + 1);
  vector<ask> now;
  for (int i = 1; i <= n; i++) {
    for (auto [ql, qr, v0, id] : buc[i]) {
      if (!now.empty() && (ql - now.front().l >= BQ || (int)now.size() >= BQ)) solveall(exchange(now, {}));
      now.push_back({ql, qr, hua(v0), id});
    }
  }
  solveall(now);
  for (int i = 1; i <= q; i++) cout << mxv - 1 - fans[i] << endl;
  fprintf(stderr, "ccnt = %d, bcnt = %d, dcnt = %d\n", ccnt, bcnt, dcnt);
  return 0;
}