题解：P10689 SuperMemo

tangtianyao0123 · 2026-03-06 19:47:29 · 题解

神秘平衡树，调的五年级蒟蒻畏惧了。

题目传送门。

大概就是让你维护一个序列，需要支持区间加，区间反转，区间右移，插入删除，求区间最小值的操作。

首先插入删除求最小值都是很基础的，随便用 FHQ 维护一下就行了。
然后区间反转其实就是这个，打个反转 tag 即可。

然后区间加只需要效仿线段树打个加法 tag 即可。所以重点就是区间右移。

不难发现，对于区间 [l,r]，右移 (r - l + 1) 次和没右移是没有区别的。因此如果需要右移 z 次，z\gets z\bmod (r - l + 1) 即可。然后找找规律，就知道其实只是将 [l,r-d] 和 [r-d+1,r] 交换了一下，所以只需要分裂出来之后交换顺序合并即可。总时间复杂度 O(m\log n)。

上代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;

int n, a, q, x, y, z;
int root, idx, val[N], rd[N], sz[N], mi[N], ls[N], rs[N], rev[N], add[N];
string op;

void pushup(int u){
  sz[u] = sz[ls[u]] + sz[rs[u]] + 1;
  mi[u] = min({val[u], mi[ls[u]], mi[rs[u]]});
}

void pushdown(int u){
  if(rev[u]){
    swap(ls[u], rs[u]);
    rev[ls[u]] ^= 1;
    rev[rs[u]] ^= 1;
    rev[u] = 0;
  }
  if(add[u]){
    if(ls[u]){
      add[ls[u]] += add[u];
      mi[ls[u]] += add[u];
      val[ls[u]] += add[u];
    }
    if(rs[u]){
      add[rs[u]] += add[u];
      mi[rs[u]] += add[u];
      val[rs[u]] += add[u];
    }
    add[u] = 0;
  }
}

void split(int u, int k, int &a, int &b){
  if(!u){
    a = b = 0;
    return ;
  }
  pushdown(u);
  if(sz[ls[u]] < k){
    a = u;
    split(rs[u], k - sz[ls[u]] - 1, rs[u], b);
  }else{
    b = u;
    split(ls[u], k, a, ls[u]);
  }
  pushup(u);
}

int merge(int a, int b){
  if(!a || !b) return a ^ b;
  pushdown(a), pushdown(b);
  if(rd[a] < rd[b]){
    rs[a] = merge(rs[a], b);
    pushup(a);
    return a;
  }else{
    ls[b] = merge(a, ls[b]);
    pushup(b);
    return b;
  }
}

void Add(int x, int y, int z){
  int a, b, c;
  split(root, y, b, c);
  split(b, x - 1, a, b);
  add[b] += z;
  mi[b] += z;
  val[b] += z;
  root = merge(merge(a, b), c);
}

void reverse(int x, int y){
  int a, b, c;
  split(root, y, b, c);
  split(b, x - 1, a, b);
  rev[b] ^= 1;
  root = merge(merge(a, b), c);
}

void revolve(int x, int y, int z){
  z %= (y - x + 1);
  int a, b, c, d;
  split(root, y, c, d);
  split(c, x - 1, a, c);
  split(c, y - x + 1 - z, b, c);
  root = merge(merge(merge(a, c), b), d);
}

void insert(int x, int y){
  val[++idx] = y, rd[idx] = rand(), sz[idx] = 1, mi[idx] = y;
  int a, b;
  split(root, x, a, b);
  root = merge(merge(a, idx), b);
}

void Delete(int x){
  int a, b, c;
  split(root, x - 1, a, b);
  split(b, 1, b, c);
  root = merge(a, c);
}

int query(int x, int y){
  int a, b, c;
  split(root, y, b, c);
  split(b, x - 1, a, b);
  int ans = mi[b];
  root = merge(merge(a, b), c);
  return ans;
}

signed main(){
  ios::sync_with_stdio(0); cin.tie(0);
  mi[0] = 1e18;
  srand(time(0));
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a;
    insert(i - 1, a);
  }
  cin >> q;
  while(q--){
    cin >> op >> x;
    if(op == "ADD"){
      cin >> y >> z;
      Add(x, y, z);
    }else if(op == "REVERSE"){
      cin >> y;
      reverse(x, y);
    }else if(op == "REVOLVE"){
      cin >> y >> z;
      revolve(x, y, z);
    }else if(op == "INSERT"){
      cin >> y;
      insert(x, y);
    }else if(op == "DELETE"){
      Delete(x);
    }else if(op == "MIN"){
      cin >> y;
      cout << query(x, y) << '\n';
    }
  }
  return 0;
}