2009 Niuke Summer Multi-School Training Camp (Game 7)
Find the median

Title: Processing the input first, there's nothing wrong with it. After processing, it should be equivalent to adding all the numbers between L and R in a set at a time, asking what the median is.
Solution: This problem is interesting. It can be done by discretization + line segment tree, which is equivalent to finding the sum/2 number on line segment tree. Simpler is to save all l and r, then discretize them, and then insert and delete the discretized values. I wrote a direct discretization operation on the line segment tree according to the operation of dynamic opening point of the line segment tree, which is a bit like the combination of dynamic opening point and discretization.
Generally speaking, which interval is needed, I will open the next node of the line tree to what kind of l,r, not necessarily exactly half of it. It's easy to get stuck because it can degrade to n2n^2n2 complexity.

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;


const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 4e7 + 5;
const int MX = 4e5 + 10;
const int INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;
#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

LL n;
LL x1, x2, a1, b1, c1, m1, Y1, y2, a2, b2, c2, m2;
LL ls[MX], rs[MX], xs[MX], ys[MX];

struct node {
    int l;
    int r;
    int num;
    LL sum;
    int ls, rs;
} dat[maxn];
int cnt;

int init(int l, int r, int k) {
    dat[k].l = l;
    dat[k].r = r;
    dat[k].sum = 0;
    dat[k].num = 0;
    dat[k].ls = -1;
    dat[k].rs = -1;
    return k;
}

void build(int l, int r, int k) {
    cnt = 0;
    init(l, r, cnt++);
}

void add(int k, int num) {
    dat[k].num += num;
    dat[k].sum += 1LL * (dat[k].r - dat[k].l + 1) * num;
}

void pushdown(int k) {
    add(dat[k].ls, dat[k].num);
    add(dat[k].rs, dat[k].num);
    dat[k].num = 0;
    dat[k].sum = dat[dat[k].ls].sum + dat[dat[k].rs].sum;
}

void update(int a, int b, int k) {
    if (b < dat[k].l || a > dat[k].r)return;
    if (a <= dat[k].l && dat[k].r <= b) {
        dat[k].num++;
        dat[k].sum += dat[k].r - dat[k].l + 1;
    } else {
        if (dat[k].ls == -1) {
            int mid;
            if (b <= dat[k].r) {
                mid = b;
            } else mid = a;
            if (mid == dat[k].l) {  //What points do you need?
                dat[k].ls = init(dat[k].l, mid, cnt++);
                dat[k].rs = init(mid + 1, dat[k].r, cnt++);
            } else {
                dat[k].ls = init(dat[k].l, mid - 1, cnt++);
                dat[k].rs = init(mid, dat[k].r, cnt++);
            }
        }
        pushdown(k);
        update(a, b, dat[k].ls);
        update(a, b, dat[k].rs);
        dat[k].sum = dat[dat[k].ls].sum + dat[dat[k].rs].sum;
    }
}

int querry(int k, LL x) {
    if (dat[k].ls == -1) {
        return dat[k].l + (x + dat[k].num - 1) / dat[k].num - 1;
    } else {
        pushdown(k);
        if (dat[dat[k].ls].sum >= x) {
            return querry(dat[k].ls, x);
        } else return querry(dat[k].rs, x - dat[dat[k].ls].sum);
    }
}


int main() {
    f();
    scanf("%lld", &n);
    scanf("%lld%lld%lld%lld%lld%lld", &x1, &x2, &a1, &b1, &c1, &m1);
    scanf("%lld%lld%lld%lld%lld%lld", &Y1, &y2, &a2, &b2, &c2, &m2);
    ls[1] = min(x1, Y1) + 1, rs[1] = max(x1, Y1) + 1;
    ls[2] = min(x2, y2) + 1, rs[2] = max(x2, y2) + 1;
    xs[1] = x1, ys[1] = Y1;
    xs[2] = x2, ys[2] = y2;
    for (int i = 3; i <= n; ++i) {
        xs[i] = (1LL * a1 * xs[i - 1] + 1LL * b1 * xs[i - 2] + c1) % m1;
        ys[i] = (1LL * a2 * ys[i - 1] + 1LL * b2 * ys[i - 2] + c2) % m2;
        ls[i] = min(xs[i], ys[i]) + 1;
        rs[i] = max(xs[i], ys[i]) + 1;
    }
    LL mi = 1e9 + 1, mx = -1;
    for (int i = 1; i <= n; ++i) {
        mx = max(mx, rs[i]);
        mi = min(mi, ls[i]);
    }

    LL S = 0;
    build(mi, mx, 0);
    for (LL i = 1; i <= n; i++) {
        S += rs[i] - ls[i] + 1;
        update(ls[i], rs[i], 0);
        printf("%d\n", querry(0, (S+1) / 2));
    }
    return 0;
}