The crazy helix

                            Solution in C :

In   C++   :







#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <queue>
#include <math.h>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <bitset>
#include <ctype.h>
#include <cassert>
#include <stack>
#include <fstream>
#include <unordered_set>

using namespace std;

#define snd second
#define fst first
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define left _left
#define y1 _y1

template < typename T > T abs(T x)
{
return x > 0 ? x : -x;
}

struct node
{
node *l, *r, *p;
int key, pr;
int size;

bool rev;

node()
{
l = r = p = NULL;
pr = rand();
size = 1;
rev = false;
}

void push()
{
if (rev)
{
if (l)
    l->rev ^= 1;
if (r)
    r->rev ^= 1;
swap(l, r);
rev = false;
}
}

void update()
{
size = 1 + (l ? l->size : 0) + (r ? r->size : 0);
}
};

int getSize(node *v)
{
return v ? v->size : 0;
}

typedef node* pnode;

pnode merge(pnode l, pnode r)
{
if (!l || !r)
return l ? l : r;

l->push();
r->push();

if (l->pr > r->pr)
{
l->r = merge(l->r, r);
l->r->p = l;
l->update();
return l;
}
else
{
r->l = merge(l, r->l);
r->l->p = r;
r->update();
return r;
}
}

void split(pnode v, pnode &l, pnode &r, int key)
{
if (!v)
{
l = r = NULL;
return;
}

v->push();
v->p = NULL;

if (1 + getSize(v->l) <= key)
{
l = v;
split(l->r, l->r, r, key - 1 - getSize(v->l));
if (l->r)
l->r->p = l;
}
else
{
r = v;
split(r->l, l, r->l, key);
if (r->l)
r->l->p = r;
}

if (l)
l->update();
if (r)
r->update();
}

const int maxn = 100005;

node *a[maxn];

int main(int argc, char *argv[])
{
//freopen("a.in", "r", stdin);

int n, q;
scanf("%d %d", &n, &q);

a[0] = new node();
a[0]->key = 0;

node *root = a[0];

for (int i = 1; i < n; i++)
{
node *v = new node();
v->key = i;
a[i] = v;
root = merge(root, v);
}

for (int i = 0; i < q; i++)
{
int type;
scanf("%d", &type);

if (type == 1)
{
int u, v;
scanf("%d %d", &u, &v);

pnode left, center, right;
split(root, left, right, u - 1);
split(right, center, right, v - u + 1);

center->rev ^= 1;

root = merge(merge(left, center), right);
}
else if (type == 3)
{
int u;
scanf("%d", &u);

pnode left, center, right;
split(root, center, right, u);
split(center, left, center, u - 1);

printf("element at position %d is %d\n", u, center->key + 1);

root = merge(merge(left, center), right);
}
else
{
int u;
scanf("%d", &u);

node *v = a[u - 1];

vector < pnode > b;

while (v != NULL)
{
b.pb(v);
v = v->p;
}

for (int j = b.size() - 1; j >= 0; j--)
{
b[j]->push();
}

v = a[u - 1];

int ans = getSize(v->l) + 1;

while (v->p != NULL)
{
if (v->p->r == v)
{
ans += getSize(v->p->l) + 1;
}

v = v->p;
}

printf("element %d is at position %d\n", u, ans);
}
}

return 0;
}









In   Java  :






import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Random;

public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve()
{
int n = ni(), Q = ni();
Node root = null;
Node[] nodes = new Node[n];
for(int i = n;i >= 1;i--){
nodes[i-1] = new Node(i);
root = insert(root, 0, nodes[i-1]);
}

for(int q = 0;q < Q;q++){
int type = ni();
if(type == 1){
int a = ni()-1, b = ni()-1;
if(a <= b){
root = reverse(root, a, b+1);
}else{
Node[] sp = split(root, b+1);
root = merge(sp[1], sp[0]);
root = reverse(root, n-(b+1+n-a), n);
sp = split(root, n-b-1);
root = merge(sp[1], sp[0]);
}
}else if(type == 2){
int a = ni()-1;
int x = index(nodes[a]);
out.println("element " + (a+1) + 
" is at position " + (x+1));
}else{
int a = ni()-1;
int x = get(root, a).v;
out.println("element at position " + 
(a+1) + " is " + x);
}
}
}

public static Random gen = new Random();

static public class Node
{
public int v; // value
public long priority;
public Node left, right, parent;

public int count;

public boolean rev;

public Node(int v)
{
this.v = v;
priority = gen.nextLong();
update(this);
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Node [v=");
builder.append(v);
builder.append(", count=");
builder.append(count);
builder.append(", parent=");
builder.append(parent != null ? parent.v : "null");
builder.append(", rev=");
builder.append(rev);
builder.append("]");
return builder.toString();
}
}

public static Node update(Node a)
{
if(a == null)return null;
a.count = 1;
if(a.left != null)a.count += a.left.count;
if(a.right != null)a.count += a.right.count;
return a;
}

public static Node reverse(Node a, int L, int R)
{
Node[] MR = split(a, R);
Node[] LM = split(MR[0], L);
if(LM[1] != null)LM[1].rev ^= true;
return merge(merge(LM[0], LM[1]), MR[1]);
}

public static void fall(Node a)
{
if(a == null)return;
if(a.rev){
Node n = a.left; a.left = a.right; a.right = n;
if(a.left != null)a.left.rev ^= true;
if(a.right != null)a.right.rev ^= true;
a.rev = false;
}

if(a.left != null){
update(a.left);
}
if(a.right != null){
update(a.right);
}
update(a);
}

public static Node disconnect(Node a)
{
if(a == null)return null;
a.left = a.right = a.parent = null;
return update(a);
}

public static Node merge(Node a, Node b)
{
if(b == null)return a;
if(a == null)return b;
if(a.priority > b.priority){
fall(a);
setParent(a.right, null);
setParent(b, null);
a.right = merge(a.right, b);
setParent(a.right, a);
return update(a);
}else{
fall(b);
setParent(a, null);
setParent(b.left, null);
b.left = merge(a, b.left);
setParent(b.left, b);
return update(b);
}
}

public static int count(Node a)
{
return a == null ? 0 : a.count;
}

public static void setParent(Node a, Node par)
{
if(a != null)a.parent = par;
}

// [0,K),[K,N)
public static Node[] split(Node a, int K)
{
if(a == null)return new Node[]{null, null};
fall(a);
if(K <= count(a.left)){
setParent(a.left, null);
Node[] s = split(a.left, K);
a.left = s[1];
setParent(a.left, a);
s[1] = update(a);
return s;
}else{
setParent(a.right, null);
Node[] s = split(a.right, K-count(a.left)-1);
a.right = s[0];
setParent(a.right, a);
s[0] = update(a);
return s;
}
}

public static Node insert(Node a, int K, Node b)
{
if(a == null)return b;
fall(a);
if(b.priority < a.priority){
if(K <= count(a.left)){
a.left = insert(a.left, K, b);
setParent(a.left, a);
}else{
a.right = insert(a.right, K-count(a.left)-1, b);
setParent(a.right, a);
}
return update(a);
}else{
Node[] ch = split(a, K);
b.left = ch[0]; b.right = ch[1];
setParent(b.left, b);
setParent(b.right, b);
return update(b);
}
}

// delete K-th
public static Node erase(Node a, int K)
{
if(a == null)return null;
fall(a);
if(K < count(a.left)){
a.left = erase(a.left, K);
setParent(a.left, a);
return update(a);
}else if(K == count(a.left)){
setParent(a.left, null);
setParent(a.right, null);
Node aa = merge(a.left, a.right);
disconnect(a);
return aa;
}else{
a.right = erase(a.right, K-count(a.left)-1);
setParent(a.right, a);
return update(a);
}
}

public static Node get(Node a, int K)
{
while(a != null){
fall(a);
if(K < count(a.left)){
a = a.left;
}else if(K == count(a.left)){
break;
}else{
K = K - count(a.left)-1;
a = a.right;
}
}
return a;
}

public static int index(Node a)
{
if(a == null)return -1;
List<Node> nodes = new ArrayList<Node>();
for(Node x = a;x != null;x = x.parent)nodes.add(x);
for(int i = nodes.size()-1;i >= 0;i--){
fall(nodes.get(i));
}

int ind = count(a.left);
while(a != null){
Node par = a.parent;
if(par != null && par.right == a){
ind += count(par.left) + 1;
}
a = par;
}
return ind;
}

public static Node[] nodes(Node a)

 { return nodes(a, new Node[a.count], 0, a.count); }
public static Node[] nodes(Node a, Node[] ns, int L, int R)
{
if(a == null)return ns;
nodes(a.left, ns, L, L+count(a.left));
ns[L+count(a.left)] = a;
nodes(a.right, ns, R-count(a.right), R);
return ns;
}

public static String toString(Node a, String indent)
{
if(a == null)return "";
StringBuilder sb = new StringBuilder();
sb.append(toString(a.left, indent + "  "));
sb.append(indent).append(a).append("\n");
sb.append(toString(a.right, indent + "  "));
return sb.toString();
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : 
new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;

try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); }
 catch (IOException e) 
 { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c) 
{ return !(c >= 33 && c <= 126); }
private static int skip()
 { int b; while((
b = readByte()) != -1 && isSpaceChar(b)); return b; }

private static double nd()
 { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b)))
{ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !(
(b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !(
(b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static void tr(Object... o) 
{ if(INPUT.length() != 0)
System.out.println(Arrays.deepToString(o)); }
}











In    C   :







#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int size, rev, key;
struct Node *left, *right, *parent, *haxx;
} Node;

static Node *NODES;

static inline int size(Node *n) {
return n ? n->size : 0;
}

static inline void resize(Node *n) {
if (n) {
n->size = size(n->left) + size(n->right) + 1;
}
}

static inline Node *createNode(int key, Node *left, Node *right) {

Node *n = &NODES[key];

if (left) {
left->parent = n;
}
if (right) {
right->parent = n;
}
n->key = key;
n->left = left;
n->right = right;
n->rev = 0;
n->parent = NULL;
n->haxx = NULL;
resize(n);

return n;
}

static inline void pushDown(Node *n) {

Node *tmp;

if (!(n && n->rev)) {
return;
}
if (n->left) {
n->left->rev ^= 1;
}
if (n->right) {
n->right->rev ^= 1;
}
tmp = n->left;
n->left = n->right;
n->right = tmp;
n->rev = 0;
}

static inline int indexOf(Node *n) {
Node *np = n, *p;
int i;
while (np->parent) {
np->parent->haxx = np;
np = np->parent;
}
while (np != n) {
pushDown(np);
np = np->haxx;
}
pushDown(n);

i = size(n->left);
while (n->parent) {
np = n->parent;
if (n == np->right) {
i += size(np->left) + 1;
}
n = np;
}
return i;
}

static inline Node *kthChild(Node *n, int k) {
int ls;
while (1) {
pushDown(n);
ls = size(n->left);
if (k < ls) {
n = n->left;
} else if (k > ls) {
n = n->right;
k = k - ls - 1;
} else {
return n;
}
}
}

static inline Node *zig(Node *n) {
Node *left, *lr;
pushDown(n->left);
left = n->left;
lr = left->right;
left->right = n;
left->parent = n->parent;
n->parent = left;
n->left = lr;
if (lr) lr->parent = n;
resize(n);
resize(left);
return left;
}

static inline Node *zag(Node *n) {
Node *right, *rl;
pushDown(n->right);
right = n->right;
rl = right->left;
right->left = n;
right->parent = n->parent;
n->parent = right;
n->right = rl;
if (rl) rl->parent = n;
resize(n);
resize(right);
return right;
}

static inline Node *splay(Node *p, Node *n) {
Node *swap, *np, *gp;

while (1) {
np = n->parent;
if (p == np) { // hehe
return n;
}
gp = np->parent;
pushDown(gp);
pushDown(np);
swap = (n == np->left) ? zig(np) : zag(np);
if (gp) {
if (np == gp->left) {
gp->left = swap;
} else {
gp->right = swap;
}
}
n = swap;
}
}

static inline Node *reverseInterval(Node *root, int a, int b) {
Node *left, *right, *rl;
left = kthChild(root, a - 1);
right = kthChild(root, b + 1);
root = splay(NULL, left);
root->right = splay(root, right);
rl = root->right->left;
pushDown(rl);
rl->rev = 1;

return root;
}

static inline Node *splayTree(int min, int max) {
int mid;
if (min < max) {
mid = min + ((max - min) >> 1);
return createNode(mid, splayTree(min, mid - 1), splayTree(mid + 1, max));
} else if (min == max) {
return createNode(min, NULL, NULL);
} else {
return NULL;
}
}

int main(int argc, char *argv[]) {
int N, Q, q, a, b;
scanf("%d%d", &N, &Q);

NODES = malloc(sizeof(Node) * (N + 2));
Node *root = splayTree(0, N + 1);

while (Q--) {
scanf("%d", &q);
switch (q) {
case 1:
scanf("%d%d", &a, &b);
root = reverseInterval(root, a, b);
break;
case 2:
scanf("%d", &a);
printf("element %d is at position %d\n", a, indexOf(&NODES[a]));
break;
case 3:
scanf("%d", &b);
printf("element at position %d is %d\n", b, kthChild(root, b)->key);
break;
}
}
return 0;
}









In    Python3  :








def size(node):
    if node:
        return node.size
    return 0


class Node:
        
    def __init__(self, id=-1):
        self.id = id
        self.left =None
        self.right =None
        self.parent = None
        self.size = 1
        self.rev = False

    def release(self):
        if self.rev:
            self.rev = False
            self.left, self.right = self.right, self.left
            if self.left:
                self.left.rev ^= True
            if self.right:
                self.right.rev ^= True

    def update(self):
        self.size = 1 + size(self.left) + size(self.right)


def zig(p):
    q = p.parent
    r = q.parent
    q.left=p.right
    if q.left:
        q.left.parent = q
    p.right = q
    q.parent = p
    p.parent=r
    
    if p.parent:
        if r.left == q:
            r.left = p
        if r.right == q:
            r.right = p
    q.update()


def zag(p):
    q = p.parent
    r = q.parent
    q.right=p.left
    if q.right:
        q.right.parent = q
    p.left = q
    q.parent = p
    p.parent=r
    if p.parent:
        if r.left == q:
            r.left = p
        if r.right == q:
            r.right = p
    q.update()


def splay(root, p, b=None):
    p.release()
    while p.parent != b:        
        q = p.parent
        
        if q.parent == b:
            q.release()
            p.release()
            if q.left == p:
                zig(p)
            else:
                zag(p)
        else:
            r = q.parent
            r.release()
            q.release()
            p.release()
            if r.left == q:
                if q.left == p:
                    zig(q)
                    zig(p)
                else:
                    zag(p)
                    zig(p)
            elif q.left == p:
                zig(p)
                zag(p)
            else:
                zag(q)
                zag(p)
    p.update()
    if b == None:
        root = p
    else:
        b.update()
    return root


def find(k, p):
    if not p or p.size < k:
        return None
    while k:
        p.release()
        if p.left and p.left.size >= k:
            p = p.left
        else:
            if p.left:
                k -= p.left.size
            k -= 1
            if k > 0:
                p = p.right
    return p


def build( a, b):
    
    global T
    
    if a > b:
        return None
    if a == b:
        prx = T[a]
        prx.left =None
        prx.right =None 
        prx.parent = None
        
        return prx
    mid = (a + b)//2
    prx = T[mid]
    prx.parent = None

    prx.left = build( a, mid - 1)
    
    if prx.left:
        prx.left.parent = prx
    prx.right = build( mid + 1, b)
    if prx.right:
        prx.right.parent = prx
    prx.update()
    
    
    return prx


def reverse(root, a, b):
    if a == b:
        return
    lfx = a + 1
    rgx = b + 1
    prev = find(lfx - 1, root)
    nxt = find(rgx + 1, root)
    root=splay(root, prev)
    root=splay(root, nxt, prev)
    nxt.left.rev ^= True
    return root

    




n, q = map(int, input().split())

T = [None for i in range(n + 2)]
for i in range(n + 2):
    T[i] = Node(i)


root = build( 0, n + 1)

s = ''
for k in range(q):
    
    query = tuple(map(int, input().split()))
    t = query[0]
    
    if t == 1:
        i, j = query[1], query[2]
        root=reverse(root, i, j)
    
    elif t == 2:
        i = query[1]
        ptx = T[i]
        root = splay(root, ptx)
        s += 'element {} is at position {}\n'.format(i, size(ptx.left))
    
    else:
        i = query[1]
        ptx = find(i + 1,root)
        s += 'element at position {} is {}\n'.format(i, ptx.id)
print(s)