CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-21

DESCRIPTION:

\$DESCRIPTION

*/

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

//LIB

int getNumQuestions()

{

int Q;

scanf(“%d\n”,&Q);

return Q;

}

void getQuestion(int& K, int& J)

{

scanf(“%d %d\n”,&K,&J);

}

{

printf(“%d\n”,x);

}

//END LIB

struct Record{int ball,pos,where;};

#define MAXN 300000

#define MAXM 300000

int N,M;

int exchange[MAXM];

int ball[MAXN];

int counter;

Record data[MAXM*2+MAXN];

int begin[MAXN];

int end[MAXN];

int compare(const void* a,const void* b)

{

if (((Record*)a)->ball<((Record*)b)->ball)

return1;

else if (((Record*)a)->ball>((Record*)b)->ball)

return 1;

else  if ((((Record*)a)->pos)<(((Record*)b)->pos))

return1;

else return 1;

}

void swap(int& a,int& b)

{

int s=a;

a=b;

b=s;

}

int getAnswer(int K,int J)

{

int l=begin[K],r=end[K];

while (l+1!=r)

{

int mid=(l+r)>>1;

if (data[mid].pos<=J) l=mid;

else r=mid;

}

return data[l].where;

}

void prepare()

{

for (int i=0;i<N;i++)

ball[i]=i;

for (int i=0;i<N;i++)

{

data[counter].ball=i;

data[counter].pos=0;

data[counter].where=i;

counter++;

}

for (int i=0;i<M;i++)

{

data[counter].ball=ball[exchange[i]-1];

data[counter].pos=i+1;

data[counter].where=exchange[i];

counter++;

data[counter].ball=ball[exchange[i]];

data[counter].pos=i+1;

data[counter].where=exchange[i]-1;

counter++;

swap(ball[exchange[i]-1],ball[exchange[i]]);

}

qsort(data,counter,sizeof(Record),compare);

int pointer=0;

for (int i=0;i<N;i++)

{

begin[i]=pointer;

while (data[pointer].ball==i) pointer++;

end[i]=pointer;

}

}

int main()

{

scanf(“%d %d\n”,&N,&M);

for (int i=0;i<M;i++)

scanf(“%d\n”,&exchange[i]);

prepare();

int Q=getNumQuestions();

for (int i=0;i<Q;i++)

{

int K,J;

getQuestion(K,J);

}

//fclose(stdin);

//fclose(stdout);

return 0;

}