题解：AT_stpc2025_1_m Many Approaches

违规用户名576639 · 2026-05-13 14:56:38 · 题解

考虑只有 1 操作，怎么做。

如果允许离线的话，主席树是一个比较简单的做法。

但如果是在线的话，就要写可持久化主席树了，而且这种做法和 2 操作的关系不大，所以不考虑。

显然这个问题是有结合律的，考虑序列分块，记 s_{i, j} 表示 j 经过第 i 个块内的所有指令后变成的值。

考虑由于是所有不在 a_i 的位置向 a_i 走一格，所以每个人的相对顺序没有发生改变，也就是说每次位置加一的人构成一段前缀，每次位置减一的人构成一段后缀。

考虑线段树维护这个问题，那么预处理 s_{i, j} 的时间复杂度是 O(n \sqrt{m} + m \log n) 的。

对于散块直接模拟。

考虑 2 操作如何做。

本质是给定操作过后的区间，求操作前的区间。

简化问题，如果只有一个块怎么做，由于相对位置关系不变，所以通过块内的指令到达点 x 的点一定是一段区间，记这段区间为 f_{i, x}。如果有两个块怎么做，考虑变成只有一个块的问题，用第二个块的信息维护，那么 p \rightarrow f_{i + 1, p}，此时询问变为经过块内的指令到达这个区间内任意一个点的点数，用前面类似的方法处理，f_{i + 1, p} \rightarrow \bigcup \limits_{j \in f_{i + 1, p}} f_{i, j}，所以相当于要维护区间的并集，这个的维护方式是很平凡的。

对于散块而言，已知经过一条指令后的点构成的区间 [l, r]，反推前的区间，记此时是第 i 条指令。若 r < a_i，则 [l, r] \rightarrow [\max(1, l - 1), r - 1]。若 l > a_i，则 [l, r] \rightarrow [l + 1, \min(r + 1, n)]。若 l \le a_i 且 r \ge a_i，则 [l, r] \rightarrow [\max(1, l - 1), \min(n, r + 1)]。最后的答案就是区间长度。

那么你就做完了，但是直接交上去会卡常，做一些小优化。由于相对顺序不变，所以并不需要直接去记录和 f_{i, x} 相关的信息，记 g_{i, j} 为经过块 i 的指令后有多少个点的值小于等于 j。那么 \bigcup \limits_{1 \le k \le j} f_{i, k} = \{ x | 1 \le x \le g_{i, j} \}，那么只需维护 g_{i, j} 即可。

时间复杂度：O(n \sqrt{m} + m \log n + q \sqrt{m})。

空间复杂度：O(n \sqrt{m})。

虽然此处线段树清空的复杂度是线性的，但是由于常数过大，所以需要将块长调得稍微大一点，我开到了 1500。此题在 qoj 上的编号为 16238。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int B = 1500;
const int K = (N + B - 1) / B + 2;

struct Node{
  int minx, maxx;
  void Clean(){
    minx = N;
    maxx = 0;
  }
  Node operator + (const Node &b){
    return {min(minx, b.minx), max(maxx, b.maxx)};
  }
  void operator = (const Node &b){
    minx = b.minx, maxx = b.maxx;
  }
}tr[4 * N];

int n, m, q, tot, a[N], sl[K], sr[K], team[N], s[K][N], sum[K][N], lazy[4 * N];

void build(int id, int l, int r){
  lazy[id] = 0;
  if(l == r){
    tr[id] = {l, l};
    return ;
  }
  int mid = (l + r) >> 1;
  build((id << 1), l, mid);
  build(((id << 1) | 1), mid + 1, r);
  tr[id] = tr[id << 1] + tr[(id << 1) | 1];
}

void tag(int id){
  tr[id << 1].minx += lazy[id];
  tr[id << 1].maxx += lazy[id];
  tr[(id << 1) | 1].minx += lazy[id];
  tr[(id << 1) | 1].maxx += lazy[id];
  lazy[id << 1] += lazy[id];
  lazy[(id << 1) | 1] += lazy[id];
  lazy[id] = 0;
}

//小于 x 的最后一个位置
int query(int id, int l, int r, int x){
  if(l == r) return (tr[id].minx < x ? l : -1);
  int mid = (l + r) >> 1;
  tag(id);
  if(tr[(id << 1) | 1].minx < x) return query(((id << 1) | 1), mid + 1, r, x);
  return query((id << 1), l, mid, x);
}

//大于 x 的第一个位置
int query2(int id, int l, int r, int x){
  if(l == r) return (tr[id].minx > x ? l : n + 1);
  int mid = (l + r) >> 1;
  tag(id);
  if(tr[id << 1].maxx > x) return query2((id << 1), l, mid, x);
  return query2(((id << 1) | 1), mid + 1, r, x);
}

void change(int id, int l, int r, int p, int q, int num){
  if(p <= l && q >= r){
    lazy[id] += num;
    tr[id].minx += num;
    tr[id].maxx += num;
    return ;
  }
  if(r < p || l > q) return ;
  int mid = (l + r) >> 1;
  tag(id);
  change((id << 1), l, mid, p, q, num);
  change(((id << 1) | 1), mid + 1, r, p, q, num);
  tr[id] = tr[id << 1] + tr[(id << 1) | 1];
}

void record(int id, int l, int r, int pos){
  if(l == r){
    s[pos][l] = tr[id].minx;
    return ;
  }
  int mid = (l + r) >> 1;
  tag(id);
  record((id << 1), l, mid, pos);
  record(((id << 1) | 1), mid + 1, r, pos);
}

int Query(int l, int r, int p){
  if(team[l] == team[r]){
    for(int i = l; i <= r; i++){
      if(p < a[i]) p++;
      else if(p > a[i]) p--;
    }
    return p;
  }
  for(int i = l; i <= sr[team[l]]; i++){
    if(p < a[i]) p++;
    else if(p > a[i]) p--;
  }
  for(int i = team[l] + 1; i < team[r]; i++){
    p = s[i][p];
  }
  for(int i = sl[team[r]]; i <= r; i++){
    if(p < a[i]) p++;
    else if(p > a[i]) p--;
  }
  return p;
}

int Query2(int l, int r, int p){
  if(team[l] == team[r]){
    pair<int, int> seg = {p, p};
    for(int i = r; i >= l; i--){
      if(seg.second < a[i]){
        if(seg.second == 1) return 0;
        seg.second--;
        seg.first = max(1, seg.first - 1);
      }
      else if(seg.first > a[i]){
        if(seg.first + 1 > n) return 0;
        seg.first++;
        seg.second = min(n, seg.second + 1);
      }
      else{
        seg.first = max(1, seg.first - 1);
        seg.second = min(n, seg.second + 1);
        if(seg.first > seg.second) return 0;
      }
    }
    return seg.second - seg.first + 1;
  }
  pair<int, int> seg = {p, p};
  for(int i = r; i >= sl[team[r]]; i--){
    if(seg.second < a[i]){
      if(seg.second == 1) return 0;
      seg.second--;
      seg.first = max(1, seg.first - 1);
    }
    else if(seg.first > a[i]){
      if(seg.first + 1 > n) return 0;
      seg.first++;
      seg.second = min(n, seg.second + 1);
    }
    else{
      seg.first = max(1, seg.first - 1);
      seg.second = min(n, seg.second + 1);
      if(seg.first > seg.second) return 0;
    }
  }
  for(int i = team[r] - 1; i > team[l]; i--){
    if(sum[i][seg.first - 1] + 1 > sum[i][seg.second]) return 0;
    seg.first = sum[i][seg.first - 1] + 1;
    seg.second = sum[i][seg.second];
  }
  for(int i = sr[team[l]]; i >= l; i--){
    if(seg.second < a[i]){
      if(seg.second == 1) return 0;
      seg.second--;
      seg.first = max(1, seg.first - 1);
    }
    else if(seg.first > a[i]){
      if(seg.first + 1 > n) return 0;
      seg.first++;
      seg.second = min(n, seg.second + 1);
    }
    else{
      seg.first = max(1, seg.first - 1);
      seg.second = min(n, seg.second + 1);
      if(seg.first > seg.second) return 0;
    }
  }
  return seg.second - seg.first + 1;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> q;
  tot = (m + B - 1) / B;
  for(int i = 1; i <= tot; i++) sl[i] = N;
  for(int i = 1; i <= m; i++){
    cin >> a[i];
    a[i]++;
    team[i] = (i + B - 1) / B;
    sl[team[i]] = min(sl[team[i]], i);
    sr[team[i]] = i;
  }
  for(int i = 1; i <= tot; i++){
    build(1, 1, n);
    for(int j = sl[i]; j <= sr[i]; j++){
      int p = query(1, 1, n, a[j]), q = query2(1, 1, n, a[j]);
      if(p) change(1, 1, n, 1, p, 1);
      if(q <= n) change(1, 1, n, q, n, -1);
    }
    record(1, 1, n, i);
    for(int j = 1; j <= n; j++){
      sum[i][s[i][j]]++;
    }
    for(int j = 1; j <= n; j++){
      sum[i][j] += sum[i][j - 1];
    }
  }
  int ans = 0;
  for(int i = 1, t, l, r, p; i <= q; i++){
    cin >> t >> l >> r >> p;
    t = (t + ans) % 2;
    l = (l + ans) % m;
    r = (r + ans) % m;
    p = (p + ans) % n;
    if(l > r) swap(l, r);
    l++, r++, p++;
    if(t == 0){
      ans = Query(l, r, p) - 1;
      cout << ans << '\n';
    }
    else{
      ans = Query2(l, r, p);
      cout << ans << '\n';
    }
  }
  return 0;
}