[HOJ] 121 - [Interactive]串珠問題

#include<stdio.h>
#include<vector>
#include "interactive/121.h"
using namespace std;
#define N 300005
struct P{
    int x,y;
};
vector<P> s[N];
int cur[N],arr[N];
int main(){
    int n,m,i,j,t,x,y,ans,L,R,M;
    //scanf("%d%d",&n,&m);
    Init(n,m,arr);
    for(i=1;i<=n;i++){
        cur[i]=i;
        s[i].push_back((P){0,i});
    }
    for(i=1;i<=m;i++){
        //scanf("%d",&arr[i]);
        swap(cur[arr[i]],cur[arr[i]+1]);
        s[cur[arr[i]]].push_back((P){i,arr[i]});
        s[cur[arr[i]+1]].push_back((P){i,arr[i]+1});
    }
    //scanf("%d",&t);
    t=getNumQuestions();
    while(t--){
        //scanf("%d%d",&x,&y);
        getQuestion(x,y);
        L=0,R=s[x].size();
        while(L+1!=R){
            M=(L+R)/2;
            if(s[x][M].x<=y) L=M;
            else R=M;
        }
        //printf("%d\n",s[x][L].y);
        answer(s[x][L].y);
    }
}