题目描述
数轴上有 \(n\) 个点正在进行周期性的往返运动。
第 \(i\) 个点 \((1 \le i \le n)\) 的运动区间是 \([x_i, x_i + L]\)。所有点的运动区间长度相同，均为 \(L\)。
在第 \(0\) 秒时：
- 若 \(c_i = 0\)，则第 \(i\) 个点位于 \(x_i\)，且其初始运动方向向右；
- 若 \(c_i = 1\)，则第 \(i\) 个点位于 \(x_i + L\)，且其初始运动方向向左。
所有的点每秒移动 \(1\) 个单位长度。当任意一个点到达其运动区间的端点时，它会立刻调头反向移动。
现在有 \(q\) 个询问，每个询问给出时间 \(t\) 和一个整数 \(k\)，请你求出在第 \(t\) 秒时，所有点当前位置中的第 \(k\) 小值。
样例
样例输入 #1
5 4 10
0 0
7 0
3 1
12 1
20 0
0 3
3 2
12 4
20 5
样例输出 #1
13
10
15
22
样例解释 #1
对于各个询问：
- \(t = 0, k = 3\)：此时各点位置为 \(0, 7, 13, 22, 20\)。从小到大排序为 \(0, 7, 13, 20, 22\)，第 \(3\) 小值为 \(13\)。
- \(t = 3, k = 2\)：此时各点位置为 \(3, 10, 10, 19, 23\)。从小到大排序为 \(3, 10, 10, 19, 23\)，第 \(2\) 小值为 \(10\)。
- \(t = 12, k = 4\)：此时各点位置为 \(8, 15, 5, 14, 28\)。从小到大排序为 \(5, 8, 14, 15, 28\)，第 \(4\) 小值为 \(15\)。
- \(t = 20, k = 5\)：运动周期为 \(2L = 20\) 秒，此时所有点回到了第 \(0\) 秒的位置，即 \(0, 7, 13, 22, 20\)。从小到大排序后，第 \(5\) 小值为 \(22\)。
数据规模
注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。
| 子任务编号 | 分数 | \(n, q \le\) | \(L \le\) | \(t_j \le\) |
|---|---|---|---|---|
| 1 | 40 | \(2000\) | \(2000\) | \(2000\) |
| 2 | 60 | \(2 \times 10^5\) | \(10^9\) | \(10^{18}\) |
对于 \(100\%\) 的数据：
- \(1 \le n, q \le 2 \times 10^5\)
- \(1 \le L \le 10^9\)
- \(0 \le x_i \le 10^9\)
- \(c_i \in \{0, 1\}\)
- \(0 \le t_j \le 10^{18}\)
- \(1 \le k_j \le n\)
Subtask 1
对于 \(n,q \le 2000\) ，可接受 \(O(nq)\) ，对每个位置进行暴力模拟，排序输出第 \(k\) 小即可
Subtask 2
由于每个点的速度及区间长度都相同，仅有初始位置及运动方向不同，不难看出同一运动方向上的点的相对位置不变。
对于任意一个位置，经过 \(t\) 秒后，设其为从小到大第 \(i\) 个点，其左侧位置一定为第 \(i-1\) 个点，右侧一定为第 \(i+1\) 个点，考虑二分。
题目要求输出第 \(k\) 个点的位置，对位置进行二分答案。
对于每一个位置，查找 \(t\) 秒后其是否为第 \(k\) 个点，点的类型可分为往左和往右两种类型，若该位置前方往左和往右的点的和等于 \(k\)，则该点为最终答案。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 2e5+5;struct P {int x,c;
};int n,q,L;
P le[N],ri[N];
int sl,sr;inline int get_left_sum(ll val, ll t) {ll dt = (t<=L)?-t:(t-2*L); ll ans=0; int l=1,r=sl;while(l<=r) {int mid = (l+r)/2;if(le[mid].x<=val-dt) l=mid+1,ans=mid;else r=mid-1;}return ans;
}inline int get_right_sum(ll val, ll t) {ll dt = (t<=L)?t:(2*L-t); ll ans=0;int l=1,r=sr;while(l<=r) {int mid = (l+r)/2;if(ri[mid].x<=val-dt) l=mid+1,ans=mid;else r=mid-1;}return ans;
}bool cmp(P p1,P p2) {return p1.x<p2.x;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q>>L;for(int i=1;i<=n;i++) {int x,c; cin>>x>>c;if(c==0) ri[++sr]={x,c};else le[++sl]={x+L,c};}sort(ri+1,ri+1+sr,cmp);sort(le+1,le+1+sl,cmp);while(q--) {ll t,k; cin>>t>>k; t%=2*L;ll l=-2e18,r=2e18;ll ans=-1;while(l<=r) {ll mid = l+(r-l)/2;ll sum = get_left_sum(mid,t) + get_right_sum(mid,t);if(sum>=k) r=mid-1,ans=mid;else l=mid+1;}cout<<ans<<endl;}return 0;
}