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 flashmt

uses math;
const fi='';
      maxn=100010;
      oo=2000000000;
var b:array[1..maxn,0..2] of longint;
    a,g,h:array[0..maxn*5] of longint;
    c,pos,re:array[0..maxn] of longint;
    n,m:longint;

procedure init(node,l,r:longint);
var mid:longint;
begin
     if l=r then
     begin
          h[node]:=l; pos[l]:=node;
          a[node]:=c[l];
     end
     else
     begin
          mid:=(l+r) shr 1;
          init(node shl 1,l,mid);
          init(node shl 1+1,mid+1,r);
          h[node]:=h[node shl 1];
          a[node]:=max(a[node shl 1],a[node shl 1+1]);
     end;
end;

procedure rf;
var i:longint; c:char;
begin
     readln(m);
     n:=0;
     for i:=1 to m do
     begin
          readln(c,b[i,1],b[i,2]);
          if c='Q' then b[i,0]:=1
          else inc(n);
     end;
     init(1,1,n);
end;

function find(node,l,r,val:longint):longint;
var mid:longint;
begin
     if l=r then find:=l
     else
     begin
          mid:=(l+r) shr 1;
          val:=val+g[node];
          if h[node shl 1+1]<=val then
             find:=find(node shl 1+1,mid+1,r,val)
          else find:=find(node shl 1,l,mid,val);
     end;
end;

procedure incr(node,l,r,x,y:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then
     begin
          g[node]:=g[node]+1;
          h[node]:=h[node]-1;
     end
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then incr(node shl 1,l,mid,x,min(y,mid));
          if y>mid then incr(node shl 1+1,mid+1,r,max(x,mid+1),y);
          h[node]:=min(h[node shl 1],h[node shl 1+1])-g[node];
     end;
end;

procedure update(x:longint);
begin
     while x>1 do
     begin
          x:=x shr 1;
          h[x]:=min(h[x shl 1],h[x shl 1+1])-g[x];
          a[x]:=max(a[x shl 1],a[x shl 1+1]);
     end;
end;

procedure get(node,l,r,x,y:longint;var re:longint);
var mid,t,u:longint;
begin
     if (l=x) and (r=y) then re:=a[node]
     else
     begin
          mid:=(l+r) shr 1;
          t:=-oo; u:=-oo;
          if x<=mid then get(node shl 1,l,mid,x,min(y,mid),t);
          if mid<y then get(node shl 1+1,mid+1,r,max(x,mid+1),y,u);
          re:=max(t,u);
     end;
end;

procedure pr;
var i,x,y,dem:longint;
begin
     for i:=m downto 1 do
         if b[i,0]=0 then
         begin
              x:=find(1,1,n,b[i,2]);
              if x<n then incr(1,1,n,x+1,n);
              c[x]:=b[i,1];
              h[pos[x]]:=oo;
              update(pos[x]);
         end;
     fillchar(g,sizeof(g),0);
     init(1,1,n);
     dem:=0;
     for i:=m downto 1 do
         if b[i,0]=0 then
         begin
              x:=find(1,1,n,b[i,2]);
              if x<n then incr(1,1,n,x+1,n);
              h[pos[x]]:=oo; a[pos[x]]:=-oo;
              update(pos[x]);
         end
         else
         begin
              dem:=dem+1;
              x:=find(1,1,n,b[i,1]);
              y:=find(1,1,n,b[i,2]);
              get(1,1,n,x,y,re[dem]);
         end;
     while dem>0 do
     begin
          writeln(re[dem]);
          dec(dem);
     end;
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;

const int N = 1e5+7;
int bit1[2*N], m, n, st[4*N], bit2[2*N];
struct query {
    char type;
    int x, y;
    void read() {
        scanf(" %c%d%d", &type, &x, &y);
    }
} q[N];

void updateBIT(int * bit, int i, int v) {
    for(; i <= n; i += i & -i)
        bit[i] += v;
}

int findBIT(int * bit, int v) {
    int res = n;
    for(int mask = n >> 1; mask != 0 && res >= 1; mask >>= 1) {
        int t = res - mask;
        if(v <= bit[t]) res = t;
        else v -= bit[t];
    }
    return res;
}

int sumBIT(int * bit, int i) {
    int res = 0;
    for(; i != 0; i -= i & -i)
        res += bit[i];
    return res;
}

void updateST(int k, int l, int r, int u, int v) {
    if(u < l || u > r || l > r) return;
    if(l == r) st[k] = max(st[k], v);
    else {
        updateST(2*k, l, (l+r)/2, u, v);
        updateST(2*k+1, (l+r)/2+1, r, u, v);
        st[k] = max(st[2*k], st[2*k+1]);
    }
}

int getST(int k, int l, int r, int u, int v) {
    if(v < l || r < u || l > r) return st[0];
    if(u <= l && r <= v) return st[k];
    return max(getST(2*k, l, (l+r)/2, u, v), getST(2*k+1, (l+r)/2+1, r, u, v));
}

void enter() {
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        q[i].read();
        if(q[i].type == 'A') ++n;
    }
}

void standardizate() {
    while(n & (n-1)) n -= n & -n; n <<= 1;
    for(int i = 1; i <= n; ++i) updateBIT(bit2, i, 1);
    for(int i = m; i >= 1; --i)
        if(q[i].type == 'A') {
            int backup = q[i].y;
            q[i].y = findBIT(bit2, q[i].y);
            updateBIT(bit1, backup, 1);
            updateBIT(bit2, q[i].y, -1);
        } else {
            q[i].x = findBIT(bit2, q[i].x);
            q[i].y = findBIT(bit2, q[i].y);
        }
}

void solve() {
    memset(st, 0xc1, sizeof st);
    for(int i = 1; i <= m; ++i) {
        if(q[i].type == 'A')
            updateST(1, 1, n, q[i].y, q[i].x);
        else
            printf("%d\n", getST(1, 1, n, q[i].x, q[i].y));
    }
}

int main() {
    enter();
    standardizate();
    solve();
    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

const double PI = acos(-1.0);
const int oo = 1000111000;

struct Node {
    Node *ch[2];
    int p;
    int size;
    int key, maxVal;

    Node(int newKey) {
        ch[0] = ch[1] = NULL;
        size = 1;
        p = rand();
        key = maxVal = newKey;
    }
} *root;

void print2(Node *p) {
    if (!p) return ;
    print2(p->ch[0]);
    printf("%d ", p->key);
    print2(p->ch[1]);
}

void print(Node *p) {
    if (!p) { puts("Bst (0): ."); return ; }
    printf("Bst (%d): ", p->size);
    print2(p);
    puts(".");
}

void update(Node *p) {
    if (p == NULL) return ;
    p->size = 1;
    p->maxVal = p->key;
    REP(b,2) if (p->ch[b]) {
        p->size += p->ch[b]->size;
        p->maxVal = max(p->maxVal, p->ch[b]->maxVal);
    }
}

Node *rotate(Node *t, int b) {
    Node *s = t->ch[1-b]; t->ch[1-b] = s->ch[b]; s->ch[b] = t;
    update(t); update(s);
    return s;
}

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

Node *get(Node *p, int k) {
    if (!p) return p;
    if (k <= getSize(p->ch[0])) return get(p->ch[0], k);
    k -= getSize(p->ch[0])+1;
    if (!k) return p;
    return get(p->ch[1], k);
}

Node *insert(Node *p, int k, int x) {
    if (!p) return new Node(x);
    int b = !(k <= getSize(p->ch[0]) + 1);

    if (!b) p->ch[0] = insert(p->ch[0], k, x);
    else p->ch[1] = insert(p->ch[1], k - getSize(p->ch[0]) - 1, x);

    if (p->p > p->ch[b]->p) p = rotate(p, 1-b);
    update(p);
    return p;
}

Node *erase(Node *p, int k) {
    if (!p) return p;
    if (k == getSize(p->ch[0]) + 1) {
        if (!p->ch[0] && !p->ch[1]) return NULL;
        else if (!p->ch[0]) p = rotate(p, 0);
        else if (!p->ch[1]) p = rotate(p, 1);
        else p = rotate(p, p->ch[0]->p < p->ch[1]->p);
        p = erase(p, k);
    }
    else {
        if (k <= getSize(p->ch[0])) p->ch[0] = erase(p->ch[0], k);
        else p->ch[1] = erase(p->ch[1], k-getSize(p->ch[0])-1);
    }
    update(p);
    return p;
}

int getMax(Node *p, int l, int r, int u, int v) {
    if (!p || l > r) return -oo;
    if (v < l || r < u) return -oo;
    if (u <= l && r <= v) return p->maxVal;
    int mid = l + getSize(p->ch[0]);
    int res = -oo;
    if (u <= mid && mid <= v) res = p->key;
    return max(max(getMax(p->ch[0], l, mid-1, u, v), getMax(p->ch[1], mid+1, r, u, v)), res);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int q, x, y; scanf("%d\n", &q);
    while (q--) {
        char c = getchar();
        if (c == 'A') {
            scanf("%d %d\n", &x, &y);
            root = insert(root, y, x);
        }
        else {
            scanf("%d %d\n", &x, &y);
            printf("%d\n", getMax(root, 1, root->size, x, y));
        }
//        print(root);
    }
    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <utility>
#include <vector>
#define MAX_LEVEL 17
using namespace std;

int INF = (1 << 30) - 5,Q;

struct node
{
         int level,value;
         node* nextNode[MAX_LEVEL];
         int width[MAX_LEVEL];
         int maxValue[MAX_LEVEL];

         node(int _L,int _V)
         {
             level = _L;  value = _V;
             for (int i = 0; i <= level; i++)
             {
                 width[i] = 1;  nextNode[i] = NULL;  maxValue[i] = value;
             }
         }
};

int randomLevel()
{
    int L = 0;
    while (rand() % 2 < 1 && L + 1 < MAX_LEVEL) L++;
    return L;
}

struct skipList
{
       node* head;

       void init()
       {
            head = new node(MAX_LEVEL - 1,-INF);
        }

       void insert(int pos,int value)
       {
            node* A = head;
            node* link[MAX_LEVEL];

            int tmp = 0;
            for (int i = head->level; i >= 0; i--)
            {
              while (tmp + A->width[i] < pos)
              {
                tmp += A->width[i];  A = A->nextNode[i];
              }                         
              link[i] = A;
            }

            node* B = new node(randomLevel(),value);
            for (int i = 0; i <= B->level; i++)
            {
                B->nextNode[i] = link[i]->nextNode[i];
                link[i]->nextNode[i] = B;
            }

            for (int i = B->level + 1; i <= head->level; i++)
            {
                link[i]->width[i]++;
                link[i]->maxValue[i] = max(link[i]->maxValue[i],value);
            }            

            link[0]->width[0] = 1;  link[0]->maxValue[0] = link[0]->value;
            for (int i = 1; i <= B->level; i++)
            {
                link[i]->width[i] = 0;  link[i]->maxValue[i] = link[i]->maxValue[i - 1];
                node* C = link[i];
                while (C != B)
                {
                  link[i]->width[i] += C->width[i - 1];
                  link[i]->maxValue[i] = max(link[i]->maxValue[i],C->maxValue[i - 1]);
                  C = C->nextNode[i - 1];
                }
            }

            B->width[0] = 1;  B->maxValue[0] = value;
            for (int i = 1; i <= B->level; i++)
            {
                B->width[i] = 0;  B->maxValue[i] = B->maxValue[i - 1];
                node* C = B;
                while (C != B->nextNode[i])
                {
                  B->width[i] += C->width[i - 1];
                  B->maxValue[i] = max(B->maxValue[i],C->maxValue[i - 1]);
                  C = C->nextNode[i - 1];
                }
            }
        }

       int maximum(int x,int y)
       {
           node* A = head;
           int tmp = 0;
           for (int i = head->level; i >= 0; i--)
             while (tmp + A->width[i] <= x)
             {
               tmp += A->width[i];  A = A->nextNode[i];
             }

           int ret = -INF;
           int gap = y - x + 1,i = 0;
           while (gap > 0)
           {
             while (i < A->level && A->width[i + 1] <= gap) i++;
             while (A->width[i] > gap) i--;
             ret = max(ret,A->maxValue[i]);
             gap -= A->width[i];  A = A->nextNode[i];
           }
           return ret;
       }       
} S;

int main()
{
    scanf("%d\n", &Q);
    S.init();

    while (Q--)
    {
      char arg;  int x,y;
      while (1)
      {
        scanf("%c", &arg);
        if (arg == 'Q' || arg == 'A') break;
      }
      scanf("%d %d\n", &x, &y);
      if (arg == 'A') S.insert(y,x); else printf("%d\n", S.maximum(x,y));
    }
}

Code mẫu của skyvn97

#include<cstdio>
const int INF=(int)2e9;
struct node {
    int val,maxv,high,balance,nnode;
    node *parent,*left,*right;
    node(){}
    void print(void) const {
        printf("Node properties: %d|%d|%d|%d|%d\n",val,maxv,high,balance,nnode);
//      if (this->left==NULL) printf("Left null\n"); else printf("Left %d\n",this->left->val);
//      if (this->right==NULL) printf("Right null\n"); else printf("Right %d\n",this->right->val);
    }
};
node *root;
int max(const int &x,const int &y) {
    if (x>y) return (x); else return (y);
}
int max(int x,int y,int z) {
    return (max(max(x,y),z));
}
void tree_init() {
    root=NULL;
}
void treeview(node *a,int l) {
    if (a==NULL) return;
    int i;
    for (i=1;i<=l;i=i+1) printf("\t");
    printf("%d|%d|%d|%d|%d\n",a->val,a->maxv,a->high,a->balance,a->nnode);
//  system("Pause");
    for (i=1;i<=l;i=i+1) printf("\t"); 
    printf("Left\n");
    treeview(a->left,l+1);  
    for (i=1;i<=l;i=i+1) printf("\t");
    printf("Right\n");
    treeview(a->right,l+1); 
}
void create(node *&p,const int &x) {        
    if (p!=NULL) return;
    p=new node();
    p->val=x;
    p->maxv=x;
    p->high=1;
    p->balance=0;
    p->nnode=1;
    p->parent=NULL;
    p->left=NULL;
    p->right=NULL;
}
void calculate(node *p) {   
    if (p==NULL) return;
//  printf("Before %d|%d|%d|%d|%d\n",p->val,p->maxv,p->high,p->balance,p->nnode);
    int l,r;
    if (p->left==NULL) l=0; else l=p->left->high;
    if (p->right==NULL) r=0; else r=p->right->high;
    p->high=max(l,r)+1;
    p->balance=l-r;
    if (p->left==NULL) l=0; else l=p->left->nnode;
    if (p->right==NULL) r=0; else r=p->right->nnode;
    p->nnode=l+r+1;
    if (p->left==NULL) l=-INF; else l=p->left->maxv;
    if (p->right==NULL) r=-INF; else r=p->right->maxv;
    p->maxv=max(l,r,p->val);
//  printf("After %d|%d|%d|%d|%d\n",p->val,p->maxv,p->high,p->balance,p->nnode);
}
void link(node *a,node *b,int dir) {
    if (a==NULL) {
        root=b;
        if (root!=NULL) root->parent=NULL;
        return;
    }
    if (dir==1) a->left=b; else a->right=b;
    if (b!=NULL) b->parent=a;
}
void left_rotation(node *a) {
    //printf("Left rotate %d\n",a->val);
    node *b,*c;
    int dir=0;
    c=a->parent;
    if (c!=NULL) {
        if (c->left==a) dir=1;
        else dir=2;
    }
    b=a->right; 
    link(a,b->left,2);
    link(b,a,1);
    link(c,b,dir);
    calculate(a);
    calculate(b);
//  a->print();
}
void right_rotation(node *a) {
    //printf("Right rotate %d\n",a->val);
    node *b,*c;
    c=a->parent;
    int dir=0;
    if (c!=NULL) {
        if (c->left==a) dir=1;
        else dir=2;
    }
    b=a->left;  
    link(a,b->right,1);
    link(b,a,2);
    link(c,b,dir);
    calculate(a);
    calculate(b);
}
void rebalance(node *a) {
    node *c;
    while (a!=NULL) {
        calculate(a);
        c=a->parent;
        //printf("rebalancing %d\n",a->val);
        if (a->balance==2) {
            if (a->left->balance==-1) left_rotation(a->left);
            right_rotation(a);
        }
        if (a->balance==-2) {
            if (a->right->balance==1) right_rotation(a->right);
            left_rotation(a);
        }
        a=c;
    }
}
void insert(const int &i,const int &x) {
//  printf("insert %d %d\n",i,x);
    node *p,*q;
    int rem=0;
    int nleft;
    int dir=0;
    p=root;
    q=NULL;
    while (p!=NULL) {
        q=p;
        if (p->left==NULL) nleft=0; 
        else nleft=p->left->nnode;
        if (rem+nleft+1>=i) {
            p=p->left;
            dir=1;
        }
        else {
            rem+=nleft+1;
            p=p->right;
            dir=2;
        }
    }
//  if (q==NULL) printf("insert to root %d\n",dir);
//  else printf("insert to %d %d\n",q->val,dir);
    if (p==NULL) {  
        create(p,x);
        if (root==NULL) root=p;
        else {
            link(q,p,dir);
            //treeview(root);
            rebalance(p);
        }
    }
}
int maxhigh(node *a,int l,int r,int u,int v) {
//  printf("Get max %d %d %d %d\n",l,r,u,v);
//  if (a!=NULL) a->print();
//  else printf("NULL\n");
    if (l>v) return (-INF);
    if (r<u) return (-INF);
    if (l>r) return (-INF);
    if (v<u) return (-INF);
    if (a==NULL) return (-INF);
    if (u<=l && r<=v) return (a->maxv);
    int nleft;
    if (a->left==NULL) nleft=0;
    else nleft=a->left->nnode;
    int left=maxhigh(a->left,l,l+nleft-1,u,v);
    int right=maxhigh(a->right,l+nleft+1,r,u,v);
    int mid;
    if (u<=l+nleft && l+nleft<=v) mid=a->val;
    else mid=-INF;
    return (max(left,mid,right));
}
int n,q;
int maxhigh(const int &u,const int &v) {
//  printf("Answering from %d to %d\n",u,v);
    return (maxhigh(root,1,n,u,v));
}
void process(void) {
    n=0;
    tree_init();
    char c;
    int i,x,y;
    scanf("%d",&q);
    for (i=1;i<=q;i=i+1) {
        scanf(" %c",&c);
        scanf("%d",&x);
        scanf("%d",&y);
        if (c=='A') {
//          printf("Insertion started\n");
            insert(y,x);
//          treeview(root,0);
//          printf("\n");
            n++;
//          printf("Insertion completed\n");
//          system("pause");
        }
        else printf("%d\n",maxhigh(x,y));
    }   
}
int main(void) {
#ifndef ONLINE_JUDGE
    //freopen("tmp.txt","r",stdin);
#endif
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

const int BITMASK = 0xFFFFF;

template <class E> struct Treap {

    struct Node {
        Node *L, *R, *P;
        E value;
        int total;
        int rank;
        E maxvalue;
        int c;

        Node(E value) : value(value), total(1), c(0) {
            this->rank = rand() & BITMASK;
            L = R = P = NULL;
        }
        void updateTotal() {
            total = 1 + (L == NULL ? 0 : L->total) + (R == NULL ? 0 : R->total);
            maxvalue = value;
            if(L != NULL) maxvalue = max(maxvalue, L->maxvalue);
            if(R != NULL) maxvalue = max(maxvalue, R->maxvalue);
        }
    };

    Node *root;
    int count;

    Treap() {
        root = NULL;
        count = 0;
    }

    void rotateLeft(Node *node) {
        Node *a = node->R;
        Node *fa = node->P;
        node->R = a->L;
        a->L = node;
        if(node->R != NULL) node->R->P = node;
        node->P = a;
        a->P = fa;
        if(fa == NULL) root = a;
        else 
            if(fa->L == node) fa->L = a;
            else fa->R = a;
        node->updateTotal();
        a->updateTotal();
    }

    void rotateRight(Node *node) {
        Node *a = node->L;
        Node *fa = node->P;
        node->L = a->R;
        a->R = node;
        if(node->L != NULL) node->L->P = node;
        node->P = a;
        a->P = fa;
        if(fa == NULL) root = a;
        else 
            if(fa->L == node) fa->L = a;
            else fa->R = a;
        node->updateTotal();
        a->updateTotal();
    }

    void pushdown(Node *n) {
        while(n->L != NULL || n->R != NULL) {
            Node *p = n->L;
            if(p == NULL || (n->R != NULL && n->R->rank < p->rank)) p = n->R;
            if(p->rank < n->rank) {
                if(p == n->L) rotateRight(n);
                else rotateLeft(n);
            }
            else break;
        }
    }

    void pushup(Node *n) {
        while(n->P != NULL) {
            if(n->rank < n->P->rank) {
                if(n == n->P->L) rotateRight(n->P);
                else rotateLeft(n->P);
            }
            else break;
        }
    }

    void add(E value) {
        ++count;
        if(root == NULL) root = new Node(value);
        else {
            Node *p = root;
            while(true) {
                p->total++;
                bool lessoreq = !(p->value < value);
                if(lessoreq && p->L != NULL) p = p->L;
                else if(!lessoreq && p->R != NULL) p = p->R;
                else break;
            }
            bool lessoreq = !(p->value < value);
            if(lessoreq) {
                p->L = new Node(value);
                p->L->P = p;
                pushup(p->L);
            }
            else {
                p->R = new Node(value);
                p->R->P = p;
                pushup(p->R);
            }
        }
    }

    Node* find(E value) {
        Node *p = root;
        while(p != NULL) {
            bool less = value < p->value;
            bool gr = p->value < value;
            if(!less && !gr) return p;
            else if(less) p = p->L;
            else p = p->R;
        }
        return NULL;
    }

    bool contain(E value) {
        return find(value) != NULL;
    }

    void remove(E value) {
        Node *p = find(value);
        if(p != NULL) {
            --count;
            p->rank = 1<<30;
            pushdown(p);
            Node *fa = p->P;
            if(fa != NULL)
                if(p == fa->L) fa->L = NULL;
                else fa->R = NULL;
            if(fa == NULL) root = NULL;
            while(fa != NULL) {
                fa->total--;
                fa = fa->P;
            }
        }
    }

    Node* findK(int k) {
        Node *p = root;
        int onleft = 0;
        while(true) {
            int newonleft = onleft + (p->L == NULL ? 0 : p->L->total);
            if(newonleft == k) return p;
            else if(newonleft > k) p = p->L;
            else {
                onleft = newonleft + 1;
                p = p->R;
            }
        }
    }

     int toIndex(Node *n) {
        if(n == NULL) return count;
        int id = 0;
        if(n->L != NULL) id = n->L->total;
        while(n != NULL) {
            Node *p = n->P;
            if(p != NULL && p->R == n) id += (p->L == NULL ? 0 : p->L->total) + 1; 
            n = p;
        }
        return id;
    }

    Node* upperBound(Node *root, E value) {
        if(root == NULL) return NULL;
        bool less = value < root->value;
        if(less) {
            Node *r = upperBound(root->L, value);
            if(r != NULL) return r;
            else return root;
        }
        else return upperBound(root->R, value);
    }

    Node* lowerBound(Node *root, E value) {
        if(root == NULL) return NULL;
        bool leoreq = !(root->value < value); 
        if(leoreq) {
            Node *r = lowerBound(root->L, value);
            if(r != NULL) return r;
            else return root;
        }
        else return lowerBound(root->R, value);
    }

    pair<Treap,Treap> split(int m) { // first m elements -> 1 tree, remains -> 1 tree
        Treap left, right;
        if(m >= count) return make_pair(*this,Treap());
        else if(m <= 0) return make_pair(Treap(),*this);
        else {
            Node *p = findK(m);
            p->rank = -1<<30;
            pushup(p);
            left.root = p->L;
            p->L->P = NULL;
            p->L = NULL;
            p->updateTotal();
            right.root = p;
            left.count = (left.root == NULL ? 0 : left.root->total);
            right.count = (right.root == NULL ? 0 : right.root->total);
            p->rank = rand() & BITMASK;
            right.pushdown(p);
            return make_pair(left, right);
        }
    }

    Treap mergeWith(Treap tr) {
        if(tr.root == NULL) return *this;
        if(root == NULL) return tr;
        Node *p = tr.findK(0);
        p->rank = -1<<30;
        tr.pushup(p);
        p->L = root;
        root->P = p;
        p->updateTotal();
        Treap res;
        res.root = p;
        res.count = p->total;
        p->rank = rand() & BITMASK;
        res.pushdown(p);
        return res;
    }
};

Treap<int> tr;
char buf[1000];
int n, sz;

int main() {
    scanf("%d", &n);
    gets(buf);
    for(int i=0;i<n;++i) {
        gets(buf);
        int x, y;
        sscanf(buf+1, "%d%d", &x, &y);
        if(buf[0] == 'A') {
            if(sz == 0) tr.add(x);
            else {
                Treap<int>::Node *p = tr.findK((y == sz + 1) ? (sz - 1) : (y - 1));
                p->rank = 1<<30;
                tr.pushdown(p);
                Treap<int>::Node *nn = new Treap<int>::Node(x);
                if(y == sz + 1) p -> R = nn, nn->P = p;
                else p -> L = nn, nn -> P = p;
                for(Treap<int>::Node *q=nn;q!=NULL;q=q->P) q->updateTotal();
                p->rank = rand() & BITMASK;
                tr.pushup(p);
                tr.pushup(nn);
            }
            ++sz;
        }   
        else {
            Treap<int>::Node *u = tr.findK(x - 1);
            Treap<int>::Node *v = tr.findK(y - 1);
            Treap<int>::Node *p, *fa;
            for(p=u;p!=NULL;p=p->P) p->c++;
            for(p=v;p!=NULL;p=p->P) p->c++;
            int res = u->value;
            if(u->c < 2 && u->R != NULL) res = max( res, u->R->maxvalue);
            p = u;
            while(p->c < 2) {
                fa = p->P;
                if(fa->L == p) {
                    res = max( res, fa->value);
                    if(fa->c < 2 && fa->R != NULL) res = max( res, fa->R->maxvalue);
                }
                p = fa;
            }

            res = max(res, v->value);
            if(v->c < 2 && v->L != NULL) res = max( res, v->L->maxvalue);
            p = v;
            while(p->c < 2) {
                fa = p->P;
                if(fa->R == p) {
                    res = max( res, fa->value);
                    if(fa->c < 2 && fa->L != NULL) res = max( res, fa->L->maxvalue);
                }
                p = fa; 
            }

            for(p=u;p!=NULL;p=p->P) p->c--;
            for(p=v;p!=NULL;p=p->P) p->c--;

            printf("%d\n", res);
        }
    }   
    return 0;   
}