题意：给出n个孩子的初始位置，和每个孩子开始的朝向（左或者右），然后孩子的行走规则是，速度始终为1，两人相遇则两人立即转身背向而行。
现在有q次询问，每次问编号为i的孩子在时间t距离原点的距离。返回所有询问之和。
分析：我们现在用另一种方式思考这个行走模式。我们认为，当两个孩子相遇时，他们并没有背向而行，而是交换了身份，并继续保持自己的行进方向和速度。
这样以来，我们就可以认为所有人都始终保持匀速直线运动。每次询问就变成了：设询问编号为i的孩子开始所处的排名（即初始时从左往右数第几个人是他）为x，问现在排名为x的人的坐标。
这个问题可以使用二分查找来解决，用两个数组分别存储向左走的人的坐标和向右走的人的坐标。
每次二分查找这个坐标值。对于一个给定的坐标值我们分别在两个数组中找到它左边有多少人，两组在其左边的人数之和应为排名-1。
当然，在两个数组中数人数的时候有两点需要注意。一个是根据时间平移所有人的坐标。由于坐标是相对的所以不需要平移每个人，只需要反向平移我们枚举的坐标点即可。
二是在数人数的时候仍然要用到二分查找，但是可以直接调用upper_bound进行处理。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime> using namespace std; const int MOD = (int)(1e9) + ;
const int MAX_N = (int)(2e5) + ; class FindingKids {
public:
long long getSum(int, int, int, int, int);
}; long long a, b, c;
long long lkid[MAX_N];
long long rkid[MAX_N];
int lcnt, rcnt;
pair<int, int> pos[MAX_N];
int ranks[MAX_N]; void generate(int n)
{
long long p;
lcnt = rcnt = ;
set<long long> my_set;
for (int i = ; i < n; i++)
{
a = (a * b % MOD + c) % MOD;
p = a % (MOD - n + i + );
if (my_set.count(p) > )
p = MOD - n + i;
my_set.insert(p);
pos[i] = make_pair(p, i);
if (p % == )
{
rkid[rcnt++] = p;
}else
{
lkid[lcnt++] = p;
}
}
} long long work(int id, long long x)
{
long long l = min(lkid[] - x, rkid[] + x);
long long r = max(lkid[lcnt - ] - x, rkid[rcnt - ] + x);
while (l < r)
{
long long mid = l + (r - l) / ;
long long lnum = upper_bound(lkid, lkid + lcnt, mid + x) - lkid;
long long rnum = upper_bound(rkid, rkid + rcnt, mid - x) - rkid;
if (lnum + rnum < id + )
l = mid + ;
else
r = mid;
}
return abs(l);
} long long FindingKids::getSum(int n, int q, int A, int B, int C) {
a = A;
b = B;
c = C;
generate(n);
sort(pos, pos + n);
for (int i = ; i < n; i++)
{
ranks[pos[i].second] = i;
}
sort(lkid, lkid + lcnt);
sort(rkid, rkid + rcnt);
long long ret = ;
for (int i = ; i < q; i++)
{
a = (a * b % MOD + c) % MOD;
int kid = ranks[a % n];
a = (a * b % MOD + c) % MOD;
long long my_time = a;
long long temp = work(kid, my_time);
ret += temp;
}
return ret;
}