I use Splay Tree to store the deleted number and Binary Search on N.

//---------------------------------------------------------------------------

#include <stdio.h>

//---------------------------------------------------------------------------
int q[10001];

int GetPos(int x, int l, int r)
{
    if (l>=r)
        return l;
    if(q[(l+r)/2]<=x)
        return GetPos(x,(l+r)/2+1,r);
    else
        return GetPos(x,l,(l+r)/2);
}
//---------------------------------------------------------------------------
int main()
{
    int a=0;
    q[a]=2000000000;
    int n;
    char Key[2];
    int Val;
    scanf("%d%d",&n,&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s%d",&Key,&Val);
        if(Key[0]=='L')
            printf("%d\n",Val+GetPos(Val,0,a));
        else
        {
            int Pos=GetPos(Val,0,a);
                for(int i=Pos;i<a;i++)
                    q[i]--;
            for(int i=a;i>Pos;i--)
                q[i]=q[i-1];
            q[Pos]=Val;
            q[++a]=2000000000;
        }
    }
    return 0;
}
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <limits.h>
#include <assert.h>

#define FAIL *(int*)0 = 0

int a[16384];
int l[16384];
int r[16384];
int p[16384];
int h[16384];
int v[16384];
int root = -1;
int nn;

int n, m;

inline void upd(int x)
{
    h[x] = 0;
    v[x] = 1;

    if(l[x]>=0)
    {
        if(h[l[x]]+1 > h[x])
            h[x] = h[l[x]]+1;

        v[x] += v[l[x]];
    }

    if(r[x]>=0)
    {
        if(h[r[x]]+1 > h[x])
            h[x] = h[r[x]]+1;

        v[x] += v[r[x]];
    }
}

void fix(int x)
{
    while(x>=0)
    {
        int h1 = l[x]>=0 ? h[l[x]]+1 : 0;
        int h2 = r[x]>=0 ? h[r[x]]+1 : 0;

        if(h1 > h2+1 || h1==h2+1 && p[x]>=0 && r[p[x]]==x)
        {
            int a  = l[x];
            int b  = r[a];

            p[(p[x]>=0 ? l[p[x]]==x ? l[p[x]] : r[p[x]] : root) = a] = p[x];

            p[r[a]=x]=a;

            if((l[x]=b)>=0)
                p[b] = x, x = b;
        }
        else if(h2 > h1+1 || h2==h1+1 && p[x]>=0 && l[p[x]]==x)
        {
            int a = r[x];
            int b = l[a];

            p[(p[x]>=0 ? l[p[x]]==x ? l[p[x]] : r[p[x]] : root) = a] = p[x];

            p[l[a]=x]=a;

            if((r[x]=b)>=0)
                p[b] = x, x = b;
        }
        else
        {
            upd(x), x = p[x];
        }
    }
}

void add(int vv)
{
    int x;

    if(root==-1)
    {
        p[root = nn++] = -1, x = root;
    }
    else
    {
        x = root;

        for(;;)
        {
            assert(vv != a[x]);

            if(vv < a[x])
            {
                if(l[x]==-1)
                {
                    p[l[x]=nn++]=x, x=l[x];
                    break;
                }

                x = l[x];
            }
            else
            {
                if(r[x]==-1)
                {
                    p[r[x]=nn++]=x, x=r[x];
                    break;
                }

                x = r[x];
            }
        }
    }

    l[x] = r[x] = -1;
    a[x] = vv;
    fix(x);
}

inline int get(int vv)
{
    vv--;

    int cl = 1, cr = n;

    for(int x=root;x>=0;)
    {
        int nsl = a[x] - cl - (l[x]>=0 ? v[l[x]] : 0);

        if(vv < nsl)
            cr = a[x]-1, x = l[x];
        else
            vv -= nsl, cl = a[x]+1, x = r[x];
    }

    return cl+vv;
}

char c[128*1024];
int  x[128*1024];

int main()
{
//    freopen("input.txt", "r", stdin);

    scanf("%d %d", &n, &m);

    int i;
    for(i=0;i<m;i++)
    {
        char ts[4];
        scanf("%s %d", ts, x+i), c[i] = ts[0];
    }

    for(i=0;i<m;i++)
    {
        if(c[i]=='D')
            add(get(x[i]));
        else if(c[i]=='L')
            printf("%d\n", get(x[i]));
    }

    return 0;
}

Edited by author 12.08.2008 10:18

P.S: This is my custom AVL tree with only two simmetrical cases, specially for contests :)
(though it can perform at log^2(N), this rarely happens)

Edited by author 12.08.2008 10:17