RE 求助

#include <bits/stdc++.h>
using namespace std;
const int N = 10001000; 
int n, a[N], pos[N];  
struct node {
  int d, siz, rnd, tag; 
  node *ch[2], *prt; 
  inline void upd() {
    int ret = 1; 
    if(ch[0]) ret += ch[0]->siz, ch[0]->prt = this; 
    if(ch[1]) ret += ch[1]->siz, ch[1]->prt = this; 
    siz = ret; 
  }
  inline void push() {
    if(!this) return ; 
    if(!tag) return ; 
    swap(ch[0], ch[1]);
    if(ch[0]) ch[0]->tag ^= 1;
    if(ch[1]) ch[1]->tag ^= 1; 
    tag = 0; return ; 
  }
}pool[N], *cur = pool, *root, *b[N];
inline node* New(int d) { 
  node *p = cur++; p->d = d, p->siz = 1, 
  p->tag = 0, p->rnd = (rand() << 15) + rand(); 
  p->ch[0] = p->ch[1] = p->prt = 0;return p; 
}
inline int siz(node *p) { return !p ? 0 : p->siz; }
inline node *merge(node *p, node *q) {
  p->push(), q->push(); 
  if(!p || !q) return p ? p : q; 
  if(p->rnd <  q->rnd) { p->push(); p->ch[1] = merge(p->ch[1], q); p->upd(); return p; }
  if(p->rnd >= q->rnd) { q->push(); q->ch[0] = merge(p, q->ch[0]); q->upd(); return q; }
  return NULL; 
}
inline void split(node *r, int k, node *&p, node *&q) {
  if(!r) { p = q = 0; return ; } r->push(); 
  if(siz(r->ch[0]) >= k) q = r, split(r->ch[0], k, p, r->ch[0]);
  else p = r, split(r->ch[1], k - siz(p->ch[0]) - 1, r->ch[1], q); r->upd(); 
}
inline int rk(node *r, int x) {
  if(r) r->push(); 
  return !r ? 0 : (r->d >= x ? rk(r->ch[0], x) : siz(r->ch[0]) + 1 + rk(r->ch[1], x)); 
}
inline void reverse(int l, int r) {
  node *p, *q, *s; 
  split(root, l - 1, p, q); split(q, r - l + 1, q, s); 
  q->tag ^= 1; root = merge(merge(p, q), s);
}
inline int getpos(node *p) { 
  int ret = 0;  p->push(); ret += siz(p->ch[0]) + 1; 
  node *q = p; while(q) q->push(), q = q->prt;  
  while(p->prt) {  if(p->prt->ch[1] == p) ret += siz(p->prt->ch[0]) + 1; p = p->prt; }
  return ret;  
}
inline void out(node *r) {
  r->push();
  if(r->ch[0]) out(r->ch[0]); 
  printf("%d ", r->d); 
  if(r->ch[1]) out(r->ch[1]); 
}
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]); 
    b[i] = New(i); 
    root = merge(root, b[i]); 
    pos[a[i]] = i;  
  } sort(a + 1, a + n + 1); 
  // for(int i = 1; i <= n; i++) printf("%d\n", b[i]->d);
  for(int i = 1; i <= n; i++) {
    int ans = getpos(b[pos[a[i]]]);
    printf("%d ", ans); 
    if(i < ans) reverse(i, ans); 
     // out(root);printf("\n");
  } // out(root); 
  return 0; 
}