Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include <algorithm>
#include <cassert>
#include <cstdio>
using namespace std;

inline int nextInt() {
    int res = 0;
    char c;
    do {
        c = getchar_unlocked();
    } while(c < '0' || c > '9');
    do {
        res = (res << 3) + (res << 1) + c - '0';
        c = getchar_unlocked();
    } while(c >= '0' && c <= '9');
    return res;
}

inline void printInt(int x) {
    static char buffer[15];
    int last = 0;
    for(; x > 0; x /= 10)
        buffer[last++] = x % 10 + '0';
    while(--last >= 0)
        putchar_unlocked(buffer[last]);
}

class SplayTree {
    struct Node {
        Node * child[2], * parent;
        int value, size;
        bool reverse;
    } * root, * nil;

    void setChild(Node * x, Node * y, int d) {
        x->child[d] = y;
        y->parent = x;
    }

    Node * update(Node * x) {
        if(x == nil) return nil;
        x->size = x->child[0]->size + x->child[1]->size + 1;
        return x;
    }

    Node * pushDown(Node * x) {
        if(x == nil) return nil;
        if(x->reverse) {
            swap(x->child[0], x->child[1]);
            x->child[0]->reverse ^= true;
            x->child[1]->reverse ^= true;
            x->reverse = false;
        }
        return x;
    }

    Node * build(int l, int r) {
        if(l == r) return nil;
        int mid = (l + r) / 2;
        Node * at = new Node();
        at->parent = nil;
        at->reverse = false;
        setChild(at, build(l, mid), 0);
        at->value = nextInt();
        setChild(at, build(mid + 1, r), 1);
        return update(at);
    }

    int getDirection(Node * x, Node * y) {
        return x->child[0] == y ? 0 : 1;
    }

    void rotate(Node * x, int d) {
        Node * y = x->child[d];
        Node * z = x->parent;
        setChild(x, y->child[d ^ 1], d);
        setChild(y, x, d ^ 1);
        setChild(z, y, getDirection(z, x));
        update(x);
        update(y);
    }

    Node * splay(Node * x) {
        if(x == nil) return nil;
        while(x->parent != nil) {
            Node * y = x->parent;
            Node * z = y->parent;
            int dy = getDirection(y, x);
            int dz = getDirection(z, y);
            if(z == nil) {
                rotate(y, dy);
            } else if(dy == dz) {
                rotate(z, dz);
                rotate(y, dy);
            } else {
                rotate(y, dy);
                rotate(z, dz);
            }
        }
        return x;
    }

    Node * nodeAt(Node * x, int pos) {
        while(pos != pushDown(x)->child[0]->size) {
            if(pos < x->child[0]->size) {
                x = x->child[0];
            } else {
                pos -= x->child[0]->size + 1;
                x = x->child[1];
            }
        }
        return splay(x);
    }

    void split(Node * x, int left, Node * &t1, Node * &t2) {
        if(left == 0) {
            t1 = nil;
            t2 = x;
        } else {
            t1 = nodeAt(x, left - 1);
            t2 = t1->child[1];
            t1->child[1] = t2->parent = nil;
            update(t1);
        }
    }

    Node * join(Node * x, Node * y) {
        if(x == nil) return y;
        x = nodeAt(x, x->size - 1);
        setChild(x, y, 1);
        return update(x);
    }

    public:
    SplayTree(int n) {
        nil = new Node();
        nil->child[0] = nil->child[1] = nil->parent = nil;
        nil->reverse = false;
        nil->size = 0;
        root = build(0, n);
    }

    void reverse(int l, int r) {
        Node * t1, * t2, * t3;
        split(root, r, t2, t3);
        split(t2, l, t1, t2);
        t2->reverse ^= true;
        root = join(join(t1, t2), t3);
    }

    int get(int pos) {
        return (root = nodeAt(root, pos))->value;
    }
};

int main() {
    int n = nextInt();
    int m = nextInt();
    SplayTree tree (n);
    for(int i = 0; i < m; ++i) {
        int type = nextInt();
        int x = nextInt() - 1;
        if(type == 1) {
            int y = nextInt();
            tree.reverse(x, y);
        } else {
            printInt(tree.get(x));
            putchar_unlocked('\n');
        }
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int MAGIC = 200;

vector<pair<int, int> > buffer;

int a[N], newA[N];
int n, m;

int rangeSize(const pair<int, int> &it) {
    return abs(it.first - it.second) + 1;
}

void split(vector<pair<int, int> > &a, int cut) {
    int sumSize = 0;
    for (int i = 0; i < a.size(); ++i) {
        sumSize += rangeSize(a[i]);
        if (sumSize >= cut) {
            int from = a[i].first, to = a[i].second;
            a.erase(a.begin() + i);
            if (from <= to) {
                int mid = to - (sumSize - cut);
                a.insert(a.begin() + i, make_pair(mid, to));
                if (from < mid)
                    a.insert(a.begin() + i, make_pair(from, mid - 1));
            } else {
                int mid = to + (sumSize - cut);
                a.insert(a.begin() + i, make_pair(mid, to));
                if (from > mid)
                    a.insert(a.begin() + i, make_pair(from, mid + 1));
            }
            break;
        }
    }
}

void rebuild() {
    vector<pair<int, int> > block (1, {1, n});
    for (auto it : buffer) {
        split(block, it.first); split(block, it.second + 1);
        int sumSize = 0;
        int from = -1, to = -1;
        for (int i = 0; i < block.size(); ++i) {
            sumSize += rangeSize(block[i]);
            if (sumSize >= it.first && from == -1) from = i;
            if (sumSize >= it.second && to == -1) to = i;
            if (from >= 0 && to >= 0) break;
        }
        for (int i = from; i <= to; ++i) swap(block[i].first, block[i].second);
        for (int i = from, j = to; i < j; ++i, --j) swap(block[i], block[j]);
    }
    int newN = 0;
    for (auto it : block) {
        if (it.first <= it.second) {
            for (int i = it.first; i <= it.second; ++i)
                newA[++newN] = a[i];
        } else {
            for (int i = it.first; i >= it.second; --i)
                newA[++newN] = a[i];
        }
    }
    assert(newN == n);
    for (int i = 1; i <= n; ++i) a[i] = newA[i];
    buffer.clear();
}

int getIndex(int pos) {
    int ans = pos;
    for (int i = (int)buffer.size() - 1; i >= 0; --i) {
        int l = buffer[i].first, r = buffer[i].second;
        if (r < ans || ans < l) continue;
        ans = l + r - ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    while (m--) {
        int cmd; cin >> cmd;
        if (cmd == 1) {
            int l, r; cin >> l >> r;
            if (l == r) continue;
            buffer.push_back(make_pair(l, r));
            if (buffer.size() >= MAGIC) rebuild();
        } else {
            int k; cin >> k;
            cout << a[getIndex(k)] << '\n';
        }
    }
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

int n, q, a[100111];

struct Node {
    Node *left, *right, *father;
    int size, key;
} *root1, *root2, *sentinel;

void init() {
    sentinel = new Node;
    sentinel -> left = sentinel -> right = sentinel -> father = sentinel;
    sentinel -> size = 0;
    sentinel -> key = 0;
}

void setLink(Node *x, Node *y, bool left) {
    if (left) x->left = y;
    else x->right = y;
    y->father = x;
}

inline void update(Node *x) {
    x->size = x->left->size + x->right->size + 1;
}

void upTree(Node *x) {
    Node *y = x->father;
    Node *z = y->father;
    Node *tmp;

    if (y->right == x) {
        tmp = x->left;
        setLink(x, y, true);
        setLink(y, tmp, false);
    }
    else {
        tmp = x->right;
        setLink(x, y, false);
        setLink(y, tmp, true);
    }
    setLink(z, x, z->left == y);
    update(y); update(x);
}

void splay(Node *x) {
    while (1) {
        Node *y = x->father;
        if (y == sentinel) return ;
        Node *z = y->father;
        if (z != sentinel)
            if ((z->right == y) == (y->right == x)) upTree(y);
            else upTree(x);
        upTree(x);
    }
}

Node *access2(Node *p, int k) {
    if (k <= p->left->size) return access2(p->left, k);
    k -= p->left->size + 1;
    if (!k) return p;
    return access2(p->right, k);
}

Node *access(Node * &root, int k) {
    Node *res = access2(root, k);
    splay(res);
    root = res;
    return res;
}

void split(Node *r, Node * &t1, Node * &t2, int k) {
    if (k == 1) {
        t1 = sentinel;
        t2 = r;
        return ;
    }
    else if (k == r -> size + 1) {
        t1 = r;
        t2 = sentinel;
        return ;
    }
    Node *p = access(r, k);
    t1 = p->left;
    t2 = p;
    t1 -> father = t2 -> left = sentinel;
    update(t2);
}

Node *join(Node *t1, Node *t2) {
    if (t1 == sentinel) return t2;
    if (t2 == sentinel) return t1;
    while (1) {
        if (t1->right == sentinel) break;
        t1 = t1 -> right;
    }
    splay(t1);
    setLink(t1, t2, false);
    update(t1);
    return t1;
}

Node * create(int l, int r) {
    if (l > r) return sentinel;

    Node *res = new Node;
    res -> left = res -> right = res -> father = sentinel;
    int mid = l + ((r-l+1) >> 1);

    res -> size = r - l + 1;
    res -> key = a[mid];

    Node *left = create(l, mid-1);
    Node *right = create(mid+1, r);
    if (left != sentinel) setLink(res, left, true);
    if (right != sentinel) setLink(res, right, false);
    return res;
}

void print2(Node *root) {
    if (root == sentinel) return ;
    print2(root -> left);
    printf("%d ", root -> key);
    print2(root -> right);
}

void print(Node *root) {
    print2(root);
    puts("");
}

int main() {
    GN(n); GN(q); FOR(i,1,n) GN(a[i]);

    init();

    root1 = create(1, n);
    reverse(a+1, a+n+1);
    root2 = create(1, n);

    // print(root1); print(root2);

    while (q--) {
        int req; GN(req);
        if (req == 1) {
            int u1, v1, u2, v2; GN(u1); GN(v1);
            u2 = n - v1 + 1;
            v2 = n - u1 + 1;

            Node *a1, *a2, *a3;
            Node *b1, *b2, *b3;

            split(root1, a2, a3, v1+1);
            split(a2, a1, a2, u1);
            split(root2, b2, b3, v2+1);
            split(b2, b1, b2, u2);

            root1 = join(join(a1, b2), a3);
            root2 = join(join(b1, a2), b3);

            // print(root1); print(root2);
        }
        else {
            int k; GN(k);
            Node *t = access(root1, k);
            printf("%d\n", t->key);
        }
    }
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcount(s); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

typedef pair<int, int> II;
typedef pair<ll, ll> IL;

const ld PI = acos(ld(-1.0));
const ld eps = 1e-9;

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e17 + 5;
int dr[8] = {-1, +1, 0, 0};
int dc[8] = {0, 0, +1, -1};

const ll mod = 1000000007;

string problem = "nimg";
#define maxn 100005

struct Node {
    int key, size;
    bool reversed;
    Node *parent, *left, *right;
} *root, *nil;

Node *node[maxn + 1];
int n, a[maxn + 1], m, type, u, v;

void link(Node *parent, Node *child, bool left) {
    child->parent = parent;
    left ? parent->left = child : parent->right = child;
}

void update(Node *node) {
    node->size = 1 + node->left->size + node->right->size;
}

void build() {
    nil = node[0] = new Node(); nil->size = 0;
    for (int i = 1; i<= n; ++i) {
        node[i] = new Node();
        link(node[i], node[i - 1], true);
        node[i]->key = a[i];
        node[i]->right = nil;
        node[i]->size = i;
        node[i]->reversed = false;
    }
    node[n]->parent = nil;
    root = node[n];
}

void push(Node *node) {
    if (node == nil || !node->reversed) return;
    node->reversed = false;
    swap(node->left, node->right);
    node->left->reversed ^= true;
    node->right->reversed ^= true;
}

Node *find(Node *node, int i) {
    int order;
    while (true) {
        push(node);
        order = node->left->size + 1;
        if (i == order) return node;
        if (i < order) node = node->left;
        else { node = node->right; i -= order; }
    }
    return 0;
}

void uptree(Node *x) {
    Node *y = x->parent;
    Node *z = y->parent, *beta;
    if (x == y->left) {
        beta = x->right;
        link(y, beta, true);
        link(x, y, false);
    }
    else {
        beta = x->left;
        link(y, beta, false);
        link(x, y, true);
    }
    link(z, x, z->left == y);
    update(y);
    update(x);
}

void splay(Node *x) {
    Node *y, *z;
    while (true) {
        y = x->parent;
        if (y == nil) break;
        z = y->parent;
        if (z != nil) {
            if ((z->left == y) == (y->left == x)) uptree(y);
            else uptree(x);
        }
        uptree(x);
    }
}

void split(Node *tree, int i, Node *&left, Node *&right) {
    if (i == 0) {
        left = nil;
        right = tree;
        return;
    }
    Node *x = find(tree, i);
    splay(x);
    right = x->right; right->parent = nil;
    left = x; left->right = nil; update(left);
}

Node *join(Node *left, Node *right) {
    if (left == nil) return right;
    if (right == nil) return left;

    push(right);
    while (true) {
        push(left);
        if (left->right == nil) break;
        left = left->right;
    }

    splay(left);
    link(left, right, false);
    update(left);
    return left;
}

void visit(Node *node) {
    if (node == nil) return;
    push(node);
    visit(node->left);
    printf("%d ", node->key);
    visit(node->right);
}

void rotate(int l, int r) {
    Node *x, *y, *z, *t;
    split(root, r, t, z);
    split(t, l - 1, x, y);
    y->reversed ^= true;
    t = join(x, y);
    root = join(t, z);
}

int get(Node *node, int u){
    push(node);
    if(node->left->size + 1 == u) return node->key;
    else if(node->left->size >= u) return get(node->left, u);
    else return get(node->right, u - node->left->size - 1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("in.txt", "r", stdin);
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
    cin >> n >> m;
    For(i, 1, n) cin >> a[i];
    build();
    For(i, 1, m){
        cin >> type >> u;
        if(type == 1){
            cin >> v;
            if(u > v) swap(u, v);
            rotate(u, v);
        }
        else{
            cout << get(root, u) << "\n";
        }

    }

    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
class SplayTree {
    private:
    struct node {
        int val,sz;
        bool rev;
        node *parent,*child[2];
        node() {
            val=0;sz=0;rev=false;
            parent=NULL;
            REP(i,2) child[i]=NULL;
        }
        node(int v) {
            val=v;sz=1;rev=false;
            parent=NULL;
            REP(i,2) child[i]=NULL;
        }
        int getdir(node *a) const {
            REP(i,2) if (child[i]==a) return (i);
        }
        void pushdown(void) {
            if (rev) {
                swap(child[0],child[1]);
                REP(i,2) if (child[i]!=NULL) child[i]->rev=!child[i]->rev;
                rev=false;
            }
        }
        void pushup(void) {
            sz=1;
            REP(i,2) if (child[i]!=NULL) sz+=child[i]->sz;
        }
    };
    node *root;
    void link(node *a,node *b,int dir) {
        if (a==NULL) {
            root=b;
            if (root!=NULL) root->parent=NULL;
            return;
        }
        a->child[dir]=b;
        if (b!=NULL) b->parent=a;
    }
    void rotation(node *a,int dir) {
        node *b,*c;
        c=a->parent;
        int pd=0;
        if (c!=NULL) pd=c->getdir(a);
        b=a->child[dir];
        link(a,b->child[dir^1],dir);
        link(b,a,dir^1);
        link(c,b,pd);
    }
    void splay(node *a) {
        while (a->parent!=NULL) {
            if (a->parent->parent==NULL) {
                int dir=a->parent->getdir(a);
                rotation(a->parent,dir);
                a->child[dir^1]->pushup();
            }
            else {
                int dir=a->parent->getdir(a);
                int pd=a->parent->parent->getdir(a->parent);
                if (dir==pd) {
                    rotation(a->parent->parent,pd);
                    rotation(a->parent,dir);
                    a->child[dir^1]->child[pd^1]->pushup();
                    a->child[dir^1]->pushup();
                }
                else {
                    rotation(a->parent,dir);
                    rotation(a->parent,pd);
                    REP(i,2) a->child[i]->pushup();
                }
            }
            a->pushup();
        }
    }
    void find(int pos) {
        assert(root!=NULL && root->sz>=pos);
        node *p=root;
        int rem=0;
        while (true) {
            p->pushdown();
            int nl;
            if (p->child[0]==NULL) nl=0; else nl=p->child[0]->sz;
            if (rem+nl+1==pos) {
                splay(p);
                return;
            }
            if (p->child[0]!=NULL) {
                if (rem+nl>=pos) {
                    p=p->child[0];
                    continue;
                }
            }
            if (p->child[1]!=NULL) {
                if (rem+nl+1<pos) {
                    rem+=nl+1;
                    p=p->child[1];
                    continue;
                }
            }
        }
    }
    void merge(SplayTree t) {
        if (root==NULL) {
            root=t.root;
            return;
        }
        node *p=root;
        while (true) {
            p->pushdown();
            if (p->child[1]==NULL) break;
            p=p->child[1];
        }
        splay(p);
        link(root,t.root,1);
        if (root!=NULL) root->pushup();
    }
    SplayTree split(int pos) {
        if (root==NULL || root->sz<pos) return (SplayTree());
        find(pos);
        node *p=root;
        assert(!p->rev);
        link(NULL,p->child[0],0);
        link(p,NULL,0);
        p->pushup();
        return (SplayTree(p));
    }
    public:
    SplayTree() {
        root=NULL;
    }
    SplayTree(node *p) {
        root=p;
        root->parent=NULL;
    }
    void insert(int v) {
        node *p=new node(v);
        merge(SplayTree(p));
    }
    void reverse(int l,int r) {
        if (r<l) return;
        SplayTree last=split(r+1);
        SplayTree mid=split(l);
        assert(mid.root!=NULL);
        mid.root->rev=!mid.root->rev;
        merge(mid);
        merge(last);
    }
    int query(int pos) {
        find(pos);
        return (root->val);
    }
};
SplayTree T;
void process(void) {
    int n,q;
    scanf("%d",&n);
    scanf("%d",&q);
    REP(i,n) {
        int v;
        scanf("%d",&v);
        T.insert(v);
    }
    REP(i,q) {
        int t;
        scanf("%d",&t);
        if (t==1) {
            int l,r;
            scanf("%d",&l);
            scanf("%d",&r);
            T.reverse(l,r);
            //FOR(i,1,n) printf("%d ",T.query(i)); printf("\n");
        }
        else {
            int v;
            scanf("%d",&v);
            printf("%d\n",T.query(v));
        }
    }
}
int main(void) {
    process();
    return 0;
}