Implicit Treap: 배열 인덱스 기반 Treap

# Implicit Treap (Python) - 삽입, 삭제, 구간 반전
import sys
from random import randint
input = sys.stdin.readline
sys.setrecursionlimit(300000)
​
class Node:
  __slots__ = ['val', 'pri', 'sz', 'rev', 'l', 'r']
  def __init__(self, v):
      self.val = v; self.pri = randint(0, 10**9)
      self.sz = 1; self.rev = False; self.l = self.r = None
​
def sz(t): return t.sz if t else 0
​
def upd(t):
  if t: t.sz = 1 + sz(t.l) + sz(t.r)
​
def push(t):
  if not t or not t.rev: return
  t.l, t.r = t.r, t.l
  if t.l: t.l.rev ^= 1
  if t.r: t.r.rev ^= 1
  t.rev = False
​
def split(t, k):
  if not t: return None, None
  push(t)
  lsz = sz(t.l)
  if lsz >= k:
      L, R = split(t.l, k); t.l = R; upd(t); return L, t
  else:
      L, R = split(t.r, k - lsz - 1); t.r = L; upd(t); return t, R
​
def merge(l, r):
  if not l: return r
  if not r: return l
  push(l); push(r)
  if l.pri > r.pri:
      l.r = merge(l.r, r); upd(l); return l
  else:
      r.l = merge(l, r.l); upd(r); return r
​
def ins(t, pos, v):
  L, R = split(t, pos); return merge(merge(L, Node(v)), R)
​
def era(t, pos):
  L, MR = split(t, pos); M, R = split(MR, 1); return merge(L, R)
​
def rev(t, l, r):
  L, MR = split(t, l); M, R = split(MR, r - l + 1)
  if M: M.rev ^= 1
  return merge(merge(L, M), R)
​
def collect(t, res):
  if not t: return
  push(t); collect(t.l, res); res.append(t.val); collect(t.r, res)
​
n = int(input())
vals = list(map(int, input().split()))
root = None
for i, v in enumerate(vals):
  root = ins(root, i, v)
​
q = int(input())
for _ in range(q):
  tok = input().split()
  if tok[0] == 'I':
      root = ins(root, int(tok[1]), int(tok[2]))
  elif tok[0] == 'D':
      root = era(root, int(tok[1]))
  else:
      root = rev(root, int(tok[1]), int(tok[2]))
​
res = []; collect(root, res)
print(*res)

// Implicit Treap (Java) - 배열 기반 노드 풀
import java.util.*;
import java.io.*;
​
public class Main {
  static final int MAXN = 400005;
  static int[] val = new int[MAXN], pri = new int[MAXN];
  static int[] sz  = new int[MAXN], L = new int[MAXN], R = new int[MAXN];
  static boolean[] rev = new boolean[MAXN];
  static int tot = 0, root = 0;
  static Random rng = new Random(42);
​
  static int newNode(int v) {
      int t = ++tot;
      val[t] = v; pri[t] = rng.nextInt();
      sz[t] = 1; L[t] = R[t] = 0; rev[t] = false;
      return t;
  }
​
  static int getSz(int t) { return t == 0 ? 0 : sz[t]; }
​
  static void upd(int t) {
      if (t != 0) sz[t] = 1 + getSz(L[t]) + getSz(R[t]);
  }
​
  static void push(int t) {
      if (t == 0 || !rev[t]) return;
      int tmp = L[t]; L[t] = R[t]; R[t] = tmp;
      if (L[t] != 0) rev[L[t]] ^= true;
      if (R[t] != 0) rev[R[t]] ^= true;
      rev[t] = false;
  }
​
  static int[] t1 = new int[2], t2 = new int[2];
​
  static void split(int t, int k, int[] res) {
      if (t == 0) { res[0] = res[1] = 0; return; }
      push(t);
      int lsz = getSz(L[t]);
      if (lsz >= k) {
          split(L[t], k, res); L[t] = res[1]; upd(t); res[1] = t;
      } else {
          split(R[t], k - lsz - 1, res); R[t] = res[0]; upd(t); res[0] = t;
      }
  }
​
  static int merge(int a, int b) {
      if (a == 0) return b; if (b == 0) return a;
      push(a); push(b);
      if (Integer.compareUnsigned(pri[a], pri[b]) > 0) {
          R[a] = merge(R[a], b); upd(a); return a;
      } else {
          L[b] = merge(a, L[b]); upd(b); return b;
      }
  }
​
  static void ins(int pos, int v) {
      split(root, pos, t1);
      root = merge(merge(t1[0], newNode(v)), t1[1]);
  }
​
  static void era(int pos) {
      split(root, pos, t1); split(t1[1], 1, t2);
      root = merge(t1[0], t2[1]);
  }
​
  static void revRange(int l, int r) {
      split(root, l, t1); split(t1[1], r - l + 1, t2);
      if (t2[0] != 0) rev[t2[0]] ^= true;
      root = merge(merge(t1[0], t2[0]), t2[1]);
  }
​
  static StringBuilder sb = new StringBuilder();
​
  static void print(int t) {
      if (t == 0) return;
      push(t); print(L[t]); sb.append(val[t]).append(' '); print(R[t]);
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) ins(i, Integer.parseInt(st.nextToken()));
      int q = Integer.parseInt(br.readLine());
      while (q-- > 0) {
          st = new StringTokenizer(br.readLine());
          char op = st.nextToken().charAt(0);
          if (op == 'I') ins(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
          else if (op == 'D') era(Integer.parseInt(st.nextToken()));
          else revRange(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
      }
      print(root);
      System.out.println(sb);
  }
}