tc674div1b

题意：给出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;

}