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=1000000;
var n,m:longint;
    a,h,f,g:array[1..maxn shl 2] of longint;
    pos,d:array[1..maxn] of longint;

procedure add(node,l,r,x,val:longint);
var mid:longint;
begin
     if (l=x) and (r=x) then
     begin
          a[node]:=val; h[node]:=x; pos[x]:=node;
     end
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then add(node shl 1,l,mid,x,val)
          else add(node shl 1+1,mid+1,r,x,val);
          if val>a[node] then a[node]:=val;
          h[node]:=h[node shl 1];
     end;
end;

procedure rf;
var i,x:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(x);
          add(1,1,n,i,x);
     end;
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 update(node,l,r,x:longint);
var mid:longint;
begin
end;

procedure incr(node,l,r,x,y:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then
     begin
          f[node]:=f[node]+1;
          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);
          f[node]:=max(f[node shl 1],f[node shl 1+1])+g[node];
     end;
end;

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

function find2(node,l,r,val:longint):longint;
var mid:longint;
begin
     if (l=r) then find2:=l
     else
     begin
          mid:=(l+r) shr 1;
          val:=val-g[node];
          if f[node shl 1]>=val then
             find2:=find2(node shl 1,l,mid,val)
          else find2:=find2(node shl 1+1,mid+1,r,val);
     end;
end;

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

procedure pr;
var i,x,y,t,u,dem,re:longint; c:char;
begin
     readln(m); dem:=0;
     for i:=1 to m do
     begin
          read(c);
          if c='S' then
          begin
               readln(x);
               y:=find(1,1,n,x);
               a[pos[y]]:=-1; h[pos[y]]:=oo;
               if y<n then incr(1,1,n,y+1,n);
               update(pos[y]);
               dem:=dem+1;
          end
          else
          begin
               re:=-1;
               readln(x,y);
               if x>dem then
               begin
                    writeln('NONE'); continue;
               end;
               t:=find2(1,1,n,x);
               if y>=dem then u:=n
               else u:=find2(1,1,n,y+1)-1;
               get(1,1,n,t,u,re);
               if re=-1 then writeln('NONE') else writeln(re);
          end;
     end;
end;

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

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;
int MAX[4 * N], sz[4 * N], a[N];
int n, m;

#define idL (id << 1)
#define idR (idL | 1)
struct node {
    int l, r, id;
    node (int _l, int _r, int _id): l(_l), r(_r), id(_id) {}
    node left()
        {return node(l, l + r >> 1, idL);}
    node right()
        {return node((l + r >> 1) + 1, r, idR);}

    void build() {
        if (l > r) return;
        if (l == r) {
            sz[id] = 1; MAX[id] = a[l];
            return;
        }
        left().build(); right().build();
        sz[id] = r - l + 1;
        MAX[id] = max(MAX[idL], MAX[idR]);
    }

    int erase(int i) {
        if (l == r) {
            MAX[id] = -1; sz[id] = 0;
            return l;
        }
        int pos;
        if (sz[idL] >= i)
            pos = left().erase(i);
        else
            pos = right().erase(i - sz[idL]);
        sz[id]--; MAX[id] = max(MAX[idL], MAX[idR]);
        return pos;
    }

    int getMax(int i, int j) {
        if (l > r || r < i || j < l) return -1;
        if (i <= l && r <= j) return MAX[id];
        return max(left().getMax(i, j), right().getMax(i, j));
    }
};

struct fenwickTree {
    int bit[N];
    void Upd(int i) {for(; i < N; i += i & -i) bit[i]++;}
    int Get(int i) {
        int s = 0;
        for(; i; i -= i & -i) s += bit[i];
        return s;
    }
} BIT;

int bsL(int x) {
    int l = 1, r = n, k = -1;
    while (l <= r) {
        int m = l + r >> 1;
        if (BIT.Get(m) >= x) {
            k = m; r = m - 1;
        }
        else l = m + 1;
    }
    return k;
}

int bsR(int x) {
    int l = 1, r = n, k = -1;
    while (l <= r) {
        int m = l + r >> 1;
        if (BIT.Get(m) <= x) {
            k = m; l = m + 1;
        }
        else 
            r = m - 1;
    }
    return k;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    node root (1, n, 1);
    REP(i, 1, n) cin >> a[i];
    root.build();
    int ans, pos, x, y, q; char ch;
    cin >> q;
    while (q--) {
        cin >> ch;
        if (ch == 'S') {
            cin >> pos;
            pos = root.erase(pos);
            BIT.Upd(pos);
        }
        else {
            cin >> x >> y;
            if (x < 0) x = 0;
            if (y > n) y = n;
            x = bsL(x); y = bsR(y);
            if (x < 0 || y < 0) ans = -1;
            else 
                ans = root.getMax(x, y);
            if (ans == -1) cout << "NONE\n";
            else cout << ans << '\n';
        }
    }
    return 0;
}

Code mẫu của RR

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;
  SNODE         =       262144;

var
  f1,f2         :       text;
  n,m           :       longint;
  a             :       array[1..MAXN] of longint;
  sl,ln         :       array[1..snode] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        read(f1,a[i]);
    end;

procedure init(i,l,r:longint); inline;
    var
      mid:longint;
    begin
      if l=r then
        begin
          ln[i]:=a[l];
          exit;
        end;
      mid:=(l+r) shr 1;
      init(i shl 1,l,mid);
      init(i shl 1+1,mid+1,r);
      ln[i]:=max(ln[i shl 1],ln[i shl 1+1]);
    end;

function kth(u,i,l,r:longint):longint; inline;
    var
      mid:longint;
    begin
      if sl[i]=0 then
        if u<=r-l+1 then exit(l+u-1);
      mid:=(l+r) shr 1;
      if (mid-l+1-sl[i shl 1]) >= u then exit(kth(u,i shl 1,l,mid))
      else exit(kth(u-(mid-l+1-sl[i shl 1]),i shl 1+1,mid+1,r));
    end;

procedure erase(u,i,l,r:longint); inline;
    var
      mid:longint;
    begin
      if (u<l) or (r<u) then exit;
      if l=r then
        begin
          ln[i]:=-1;
          sl[i]:=1;
          exit;
        end;
      inc(sl[i]);
      mid:=(l+r) shr 1;
      erase(u,i shl 1,l,mid);
      erase(u,i shl 1+1,mid+1,r);
      ln[i]:=max(ln[i shl 1],ln[i shl 1+1]);
    end;

function get(u,i,l,r:longint):longint; inline;
    var
      mid:longint;
    begin
      if l=r then exit(l);
      mid:=(l+r) shr 1;
      if sl[i shl 1]>=u then exit(get(u,i shl 1,l,mid))
      else exit(get(u-sl[i shl 1],i shl 1+1,mid+1,r));
    end;

function getMax(u,v,i,l,r:longint):longint;
    var
      mid:longint;
    begin
      if (v<l) or (r<u) then exit(0);
      if (u<=l) and (r<=v) then exit(ln[i]);
      mid:=(l+r) shr 1;
      exit(max(getMax(u,v,i shl 1,l,mid),getMax(u,v,i shl 1+1,mid+1,r)));
    end;

procedure solve;
    var
      i,u,v:longint;
      c:char;
    begin
      inc(n);
      erase(n,1,1,n);
      init(1,1,n);
      readln(f1,m);
      for i:=1 to m do
        begin
          read(f1,c);
          if c='Q' then
            begin
              readln(f1,u,v);
              u:=get(u,1,1,n);
              v:=get(v+1,1,1,n)-1;
              v:=getMax(u,v,1,1,n);
              if v<=0 then writeln(f2,'NONE')
              else writeln(f2,v);
            end
          else //c='S'
            begin
              readln(f1,u);
              u:=kth(u,1,1,n);
              erase(u,1,1,n);
            end;
        end;
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.