题目大意
n辆车在一条数轴上，车的编号为1到n。编号为i的车坐标为a[i]，初始方向为dir[i]（左或右），初始位置两两不同。每辆车每个时刻行走距离为1。两辆车相碰时，会调转方向，继续行走，掉头不消耗时间。现在车子开始朝其方向行驶，同一个坐标允许有多辆车。现在有q个询问，给出 t,i，询问过了t时刻后，编号为i的车的坐标的绝对值。
解题思路
发现两车相撞只会交换编号，而他们的编号对当前车是没有影响的，只用考虑按原来方向可以到达当前车的车。假设刚好先后碰撞了l，r两辆车所在的位置是两辆车的中点，用的时间是距离的一半，先用一个二分求出碰了离当前车x远的车对，用倍增求出是哪对车，找到用时比t小的最大车对，分类讨论还会不会碰即可。
code
using namespace std;
LLL const mn=1e5+9,inf=1e18+7;
LLL n,q,lg2,a[
mn],dir[
mn],b[
mn],l[
mn][
20],r[
mn][
20];
LF calc(LLL x,LLL y,LLL &L,LLL &R){
L=x,R=x;
fd(i,lg2,0)if(y>=(1<<i)){
y-=(1<<i);
L=l[L][i];
R=r[R][i];
}
if((!L)||(!R))return inf;
return (a[R]-a[L])/2.0;
}
bool cmp(LLL x,LLL y){
return a[x]<a[y];
}
int main(){
freopen("collision.in","r",stdin);
freopen("collision.out","w",stdout);
scanf("%lld%lld",&n,&q);
fo(i,1,n)scanf("%lld%lld",&a[i],&dir[i]),b[i]=i;
sort(b+1,b+n+1,cmp);
LLL pre=0;
fo(i,1,n){
l[b[i]][0]=pre;
if(dir[b[i]]==1)pre=b[i];
}
pre=0;
fd(i,n,1){
r[b[i]][0]=pre;
if(dir[b[i]]==0)pre=b[i];
}
lg2=log(n)/log(2);
fo(j,1,lg2)fo(i,1,n)l[i][j]=l[l[i][j-1]][j-1],r[i][j]=r[r[i][j-1]][j-1];
fo(i,1,q){
LLL x,y;
scanf("%lld%lld",&x,&y);
LLL L=0,R=n,LL,RR;
while(L!=R){
LLL md=(L+R+1)/2;
if(calc(y,md,LL,RR)>x)R=md-1;
else L=md;
}
calc(y,L,LL,RR);
LLL fx=dir[y],L1=LL,R1=RR;
if(((dir[y]==0)&&l[LL][0])||((dir[y]==1)&&r[RR][0])){
fx=1-fx;
if(dir[y]==0)LL=l[LL][0];
else RR=r[RR][0];
}
if((a[RR]-a[LL])/2.0>x){
fx=1-fx;
LL=L1;
RR=R1;
}
LF tmp=(a[RR]+a[LL])/2.0+(x-(a[RR]-a[LL])/2.0)*((fx)?1:-1);
tmp+=1e-2*((tmp>0)?1:-1);
printf("%lld\n",abs((long long)(tmp)));
}
return 0;
}
