1678：独木桥
时间限制: 1500 ms 内存限制: 131072 KB
【题目描述】
Alice和Bob是好朋友，有一天他们带了\(n\)个孩子过独木桥。
为了方便，我们将问题抽象如下：
将独木桥看成一个长度无限长的实数轴，将每个孩子看作数轴上的一个实数点。数轴从左到右坐标不断增大。
孩子的位置用相对于数轴原点的点的坐标来表示。初始时\(n\)个点在\(n\)个互不相同的整点上。
每个点有一个初始朝向（从左向右或从右向左）。任何时刻所有的点都会以每秒1单位长度的速度匀速向所朝的方向移动。当某一时刻两个点同时移动到了同一个位置上，它们会立即改变自己的朝向（从左向右变成从右向左，反之亦然），然后继续移动。
有\(q\)次询问，每次询问给定\(k_i\)与\(t_i\)，询问在\(t_i\)秒后，孩子\(k_i\)目前的位置。
Bob无法同时关注这么多的孩子，请你帮帮他。
【输入】
第一行一个整数\(n\)表示孩子数，孩子从\(0\)开始编号。
第二行\(n\)个整数\(p_i\)，表示孩子们的初始位置。
第三行\(n\)个整数\(d_i\)，表示孩子们的初始朝向。\(d_i=0\)则初始向左，\(d_i=1\)则初始向右。
第四行一个整数\(q\)表示询问数。
接下来\(q\)行每行两个正整数\(k_i\),\(t_i\)表示一个询问，询问在\(t_i\)秒后，孩子\(k_i\)（按输入顺序）目前的位置。
【输出】
\(q\)行每行一个整数表示答案。
【输入样例】
5
1 3 5 8 9
1 1 1 0 0
3
3 2
0 7
1 5
【输出样例】
7
1
4
【数据规模及约定】
对于20%的数据，\(n,p_i,t_i≤10\)
。
另有10%的数据，\(d_i\)均相同。
另有20%的数据，\(q≤10\)。
另有15%的数据，\(t_i≤100\)。
另有20%的数据，\(n≤1000\)。
对于100%的数据，$1≤n,q≤2×10^5 ，0≤k_i<n，0≤p_i,t_i≤10^9，d_i ∈ { 0,1 } $。
首先要明的一件事，孩子不是会交位置的，也就是排序是不会变的。而会交换方向意味着直接计算位置后排序就可以得到对应次序的孩子的位置。
每次提问都排序是不现实的。而孩子分为两类，向左和向右。如果两类分开，他们不会相互碰撞，且相对位置不变，这样我们可以二分位置，在位置的基础上二分两类孩子的序号，从而判断该位置左侧有几人，就可以得出答案。
认清问题的本质是这个题的重点！
注意，孩子序号从0开始，所以最后查询时要+1
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct node
{
int no,pos,fx;
}ch[maxn];
int n,q;
int xh[maxn];
int xz[maxn],xy[maxn],xzjs,xyjs;
bool cmp(node a,node b)
{
return a.pos<b.pos;
}
int tjxz(long long pos,int t)
{
int l=0,r=xzjs-1,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(xz[mid]-t<=pos)l=mid+1,ans=mid;
else r=mid-1;
}
return ans+1;
}
int tjxy(long long pos,int t)
{
int l=0,r=xyjs-1,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(xy[mid]+t<=pos)l=mid+1,ans=mid;
else r=mid-1;
}
return ans+1;
}
bool pd(long long pos,int k,int t)
{
if(tjxz(pos,t)+tjxy(pos,t)>=k)return 1;
else return 0;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d",&ch[i].pos);
ch[i].no=i;
}
for(int i=0;i<n;++i)scanf("%d",&ch[i].fx);
sort(ch,ch+n,cmp);
for(int i=0;i<n;++i)
{
xh[ch[i].no]=i;
if(ch[i].fx==1)xy[xyjs++]=ch[i].pos;
else xz[xzjs++]=ch[i].pos;
}
scanf("%d",&q);
while(q--)
{
int k,t;
scanf("%d%d",&k,&t);
k=xh[k];
long long l=-1e9-1,r=2e9+2,ans;
while(l<=r)
{
long long mid=(l+r)>>1;
if(pd(mid,k+1,t))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
}
return 0;
}