思路

碰撞交换速度等价于穿过但身份按初始位置秩保序；左右两有序位置数组平移后求第k小，O((n+q)logn)，20万查询和大坐标。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
long long kth(const vector<long long>&a,const vector<long long>&b,int k,long long t){int lo=max(0,k-(int)b.size()),hi=min(k,(int)a.size());long long inf=LLONG_MAX/4;while(lo<=hi){int i=(lo+hi)/2,j=k-i;long long al=i?a[i-1]-t:-inf,ar=i<(int)a.size()?a[i]-t:inf,bl=j?b[j-1]+t:-inf,br=j<(int)b.size()?b[j]+t:inf;if(al>br)hi=i-1;else if(bl>ar)lo=i+1;else return max(al,bl);}return 0;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>p(n),sorted,a,b;for(auto &x:p)cin>>x;sorted=p;sort(sorted.begin(),sorted.end());for(int i=0;i<n;i++){int d;cin>>d;(d?b:a).push_back(p[i]);}sort(a.begin(),a.end());sort(b.begin(),b.end());vector<int>rank(n);for(int i=0;i<n;i++)rank[i]=lower_bound(sorted.begin(),sorted.end(),p[i])-sorted.begin()+1;int q;cin>>q;while(q--){int k;long long t;cin>>k>>t;cout<<kth(a,b,rank[k],t)<<'\n';}}