队列：二分+读入优化+优化

问题 B: 队列
时间限制: 1 Sec 内存限制: 20 MB
提交: 271 解决: 22
题目描述
NQI终于出分了，一直忐忑不安的小H飞奔到公示栏前，小H却发现老师公布了两个排行榜，分别是NQI正式选手和NQI邀请赛选手分别的排名。但小H当然想知道所有人在一起的排名啦。所以他准备将两个榜单和在一起排名。
由于NQI的特殊性，我们可以认为所有的人成绩都为正整数，并且NQI正式选手和NQI邀请赛选手都为n个人。它的成绩也与众不同，成绩的数值越小，排名就越靠前，即排名按成绩的数值从小到大排序。现在小H想知道对于一些排名对应的分数是多少，这样他好对大家的水平有一些了解。

输入格式
第1行，两个正整数n，m，分别表示人数与询问次数
第2，3行，每行n个由小到大排列的正整数，分别表示正式选手与邀请赛选手成绩
接下来m行，每行一个正整数x，表示询问排名（数据保证合法）
由于本题强制在线，记lastans为上一次的回答，初始lastans=0，x=x^lastans%(2*n)+1
输出格式
共m行，每行一个整数，表示排名对应分数
输入样例
3 2
1 2 3
2 3 4
5
3
输出样例
4
2
数据范围
20 % n<=1e5
40 % n<=1e6
100 % n<=2e6，m<=1e4 所有数据保证在int范围内

由于输入数据较大，本题附带文件已经将输入部分写好。

#include <cstdio>
#include <algorithm>
#include <iostream>
#define N 2000005
#define INF 23333333
using namespace std;
int a[N],b[N],n,m;
int lastans=0;
char xB[1<<15],*xS=xB,*xTT=xB;
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
#define isd(c) (c>='0'&&c<='9')
inline int read(){
    char xchh;
    int xaa;
    while(xchh=getc(),!isd(xchh));(xaa=xchh-'0');
    while(xchh=getc(),isd(xchh))xaa=xaa*10+xchh-'0';return xaa;
}
inline void init(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
}
inline int solve(int lc){
    int l=0; 
    int r=lc;
    if(lc>n) l=lc-n,r=n;
    int mid;
    while(l<=r){
        mid=(l+r)>>1;
        int ta=a[mid];
        int tb=b[lc-mid];
        if(ta<tb){
            if(a[mid+1]>tb) return tb;
            else l=mid+1;
        }
        else {
            if(b[lc-mid+1]>ta) return ta;
            else r=mid-1;
        }
    }   
    return max(a[mid],b[lc-mid]);
}
int main(){
    init();
    a[n+1]=b[n+1]=INF;
    lastans=0;
    int modd=2*n;
    int q;
    for(int i=1;i<=m;i++){
        q=read();
        q^=lastans;
        q=q%(2*n)+1;
        lastans=solve(q);
        printf("%d\n",lastans);
    }
    return 0;
}