题目链接：nowcoder多校7-Find the median

题意：

给一个空序列，每次向其中插入一个区间内的所有数，然后询问该序列的中位数。

题解：

首先预处理出所有操作区间，然后把区间形式改成左闭右开（方便处理），然后离散化之后建线段树，线段树的每个叶子节点维护的是一个区间，记录一个叶子节点的区间长度和线段树的区间和，然后每次查询即可。

参考代码：

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
const int MAXN = 4e5 + 5;
int n;
int a1, a2, b1, b2, c1, c2, m1, m2;
int x[MAXN], y[MAXN];
int vec[MAXN << 1], cnt = 0;
ll sum[MAXN << 5], lazy[MAXN << 5], len[MAXN << 5];
//线段树叶子节点维护的是区间，len记录区间长度
void seg_pushdown(int l, int r, int rt)
{
    if (lazy[rt])
    {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        sum[rt << 1] += lazy[rt] * len[rt << 1];
        sum[rt << 1 | 1] += lazy[rt] * len[rt << 1 | 1];
        lazy[rt] = 0;
    }
}
void seg_build(int l, int r, int rt)
{
    sum[rt] = lazy[rt] = 0;
    if (l == r)
    {
        len[rt] = vec[l + 1] - vec[l];
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(l, mid, rt << 1);
    seg_build(mid + 1, r, rt << 1 | 1);
    len[rt] = len[rt << 1] + len[rt << 1 | 1];
}
void seg_update(int L, int R, int val, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        sum[rt] += len[rt];
        lazy[rt]++;
        return;
    }
    seg_pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        seg_update(L, R, val, l, mid, rt << 1);
    if (R > mid)
        seg_update(L, R, val, mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
int seg_query(ll num, int l, int r, int rt)
{
    if (l == r)
    {
        ll p = sum[rt] / len[rt]; //区间内每个数有多少个
        if (num % p)
            return vec[l] + num / p;
        else
            return vec[l] + num / p - 1;
    }
    seg_pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if (sum[rt << 1] >= num)
        return seg_query(num, l, mid, rt << 1);
    else
        return seg_query(num - sum[rt << 1], mid + 1, r, rt << 1 | 1);
}
int main()
{
    scanf("%d", &n);
    scanf("%d%d%d%d%d%d", &x[1], &x[2], &a1, &b1, &c1, &m1);
    scanf("%d%d%d%d%d%d", &y[1], &y[2], &a2, &b2, &c2, &m2);
    for (int i = 3; i <= n; i++)
    {
        x[i] = (1ll * x[i - 1] * a1 + 1ll * x[i - 2] * b1 + c1) % m1;
        y[i] = (1ll * y[i - 1] * a2 + 1ll * y[i - 2] * b2 + c2) % m2;
    }
    for (int i = 1; i <= n; i++)
    {
        int l = min(x[i], y[i]) + 1;
        int r = max(x[i], y[i]) + 1;
        x[i] = l, y[i] = r;
        vec[++cnt] = l;
        vec[++cnt] = r + 1;
        //把区间调整为左闭右开
    }
    sort(vec + 1, vec + 1 + cnt);
    cnt = unique(vec + 1, vec + 1 + cnt) - (vec + 1);
    seg_build(1, cnt - 1, 1);
    ll tot = 0;
    for (int i = 1; i <= n; i++)
    {
        x[i] = lower_bound(vec + 1, vec + 1 + cnt, x[i]) - vec;
        y[i] = lower_bound(vec + 1, vec + 1 + cnt, y[i] + 1) - vec;
        seg_update(x[i], y[i] - 1, 1, 1, cnt - 1, 1);
        tot += vec[y[i]] - vec[x[i]];
        printf("%d\n", seg_query((tot + 1) / 2, 1, cnt - 1, 1));
    }
    return 0;
}