SRM 675 P1

const int sz = 20000;
struct query {
    int s, e, k, m, res;
} qu[105];
int qn, cnt[105];
const int mod = 1000000007;
inline bool cmp(query q1, query q2) {
    return q1.m < q2.m;
}
class LimitedMemorySeries1 {
public:
    void upd(int X) {
        int lo = 0, hi = qn - 1, md, F = qn;
        while (lo <= hi) {
            md = (lo + hi) / 2;
            if (qu[md].m < X) lo = md + 1;
            else {
                F = min(F, md);
                hi = md - 1;
            }
        }
        cnt[F]++;
    }
    long long getSum(int n, int x0, int a, int b, vector <int> q) {
        sort(q.begin(), q.end());
        qn = q.size();
        for (int i = 0; i < qn; i++) qu[i] = { 0, mod - 1, q[i], 0, mod - 1 };
        long long res = 0;
        for (int K = 0; K < 32; K++) {
            for (int i = 0; i < qn; i++) qu[i].m = (qu[i].s + qu[i].e) / 2;
            sort(qu, qu + qn, cmp);
            for (int i = 0; i < qn; i++) cnt[i] = 0;
            int qi = 0;
            long long X;
            X = x0;
            upd(X);
            for (int i = 1; i < n; i++) {
                X = (X*a + b) % mod;
                upd(X);
            }
            for (int i = 1; i < qn; i++) cnt[i] += cnt[i - 1];
            for (int i = 0; i < qn; i++) {
                if (cnt[i] > qu[i].k) qu[i].e = qu[i].m - 1, qu[i].res = min(qu[i].res, qu[i].m);
                else qu[i].s = qu[i].m + 1;
            }
        }
        for (int i = 0; i < qn; i++) res += qu[i].res;
        return res;
    }
};