E、find the median

https://ac.nowcoder.com/acm/contest/887/E

每次操作把一段连续的数字加入到数组中，每次求输出的中位数。

权值线段树维护区间个数，然后加上诡异的离散化。

1、首先将左端点，右端点加一，进行离散化，因为这里的询问要求中位数，所以不能和其他线段树题目一样离散化后每个点代表一个点，而是每个点需要代表一段区间。并且在建树的时候，每个叶子节点表示  到 之间的数字的个数。

2、更新操作，区间mark加一，并且区间的个数加上mark就可以。因为离散化后，叶子节点的区间一定是被连续更新的，不会出现更新叶子节点里面的一段数字的情况。

3、询问操作，以数字的个数作为权值，当查到叶子节点时，判一下有多少个数字的个数就可以。

4、为啥右端点要加一？为了让每段区间连续，方便后续建树

比如说现在有区间 [1,6] ， [3,10]，那么离散化后就是 [1,2,3,4] 离散化数字就是 [1,3,6,10]，此时线段树维护的叶节点就是区间[1,2],[3,5],[6,9]。

如果右端点不加一的话，似乎没有办法建出一个叶子节点代表一段区间的线段树。（大概是我太菜了），感性理解一下吧。

#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 8e5 + 5;
ll t[MAXN];
int tot = 1;
int n, qq;
struct segment_tree
{
	ll l;
	ll r;
	ll len;
	ll mark;
	ll cnt;
}que[MAXN * 4];
ll ql, qr, val;
void up(int k)
{
	que[k].cnt = que[k << 1].cnt + que[k << 1 | 1].cnt;
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark += que[k].mark;
		que[k << 1].cnt += que[k << 1].len * que[k].mark;
		que[k << 1 | 1].mark += que[k].mark;
		que[k << 1 | 1].cnt += que[k << 1 | 1].len * que[k].mark;
		que[k].mark = 0;
	}
}
void build(int left, int right, int k)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	que[k].cnt = 0;
	que[k].len = t[right + 1] - t[left];
	if (left == right)
	{
		
		return;
	}
	imid;
	build(lson);
	build(rson);
	//que[k].len = que[k << 1].len + que[k << 1 | 1].len;
	//up(k);
}
void update(int left, int right, int k)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark++;
		que[k].cnt += que[k].len;
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
ll query(int left, int right, int k)
{
	if (left == right)
		return (val - 1) / que[k].mark + t[que[k].l];
	down(k);
	imid;
	if (val <= que[k << 1].cnt)
	{
		return query(lson);
	}
	else
	{
		val -= que[k << 1].cnt;
		return query(rson);
	}
}
struct input
{
	ll l;
	ll r;
	ll x;
	ll y;
}in[MAXN];
void gen()
{
	sc("%d", &n);
	ll a1, b1, c1, m1, a2, b2, c2, m2;
	sc("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld", &in[1].x, &in[2].x, &a1, &b1, &c1, &m1, &in[1].y, &in[2].y, &a2, &b2, &c2, &m2);
	for (int i = 1; i <= n; i++)
	{
		if (i > 2)
		{
			in[i].x = (a1 * in[i - 1].x + b1 * in[i - 2].x + c1) % m1;
			in[i].y = (a2 * in[i - 1].y + b2 * in[i - 2].y + c2) % m2;
		}
		in[i].l = min(in[i].x, in[i].y) + 1;
		in[i].r = max(in[i].x, in[i].y) + 2;
		t[tot++] = in[i].l;
		t[tot++] = in[i].r;
	}
	sort(t + 1, t + tot);
	qq = unique(t + 1, t + tot) - t - 1;
}
int main()
{
	gen();
	build(1, qq, 1);
	ll cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		ql = lower_bound(t + 1, t + qq + 1, in[i].l) - t;
		qr = lower_bound(t + 1, t + qq + 1, in[i].r) - t - 1;
		update(1, qq, 1);
		cnt += in[i].r - in[i].l;
		val = (cnt + 1) / 2;
		printf("%lld\n", query(1, qq, 1));
	}
}