Find the median

Posted on | In , , ,

题目链接

题意

每次往一个集合中加如这些数字，询问中位数。

思路

很容易想到用权值线段树，查询时在树上查前一半大。
在把这些数字离散化后，意识到这些数字不能全插到树上节点中去。
可以让一个结点代表一个左闭右开的区间，这样我们维护起来是比较方便的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

const int N = 4e5 + 5;
struct que {
	int l, r;
}q[N];
vector<int> des;
#define lson rt << 1
#define rson rt << 1 | 1
#define Lson L, mid, lson
#define Rson mid + 1, R, rson
ll sum[N << 3], lazy[N << 3];
void push_up(int rt) {
	sum[rt] = sum[lson] + sum[rson];
}
inline int getv(int id) {
	return des[id - 1];
}
void build(int L, int R, int rt) {
	lazy[rt] = 0;
	if (L == R) {
		sum[rt] = 0;
		return;
	}
	int mid = (L + R) >> 1;
	build(Lson);
	build(Rson);
	push_up(rt);
}

void push_down(int rt, int L, int R) {
	if (lazy[rt]) {
		lazy[lson] += lazy[rt];
		lazy[rson] += lazy[rt];
		int mid = (L + R) >> 1;
		sum[lson] += (getv(mid + 1) - getv(L)) * 1ll * lazy[rt];
		sum[rson] += (getv(R + 1) - getv(mid + 1)) * lazy[rt];
		lazy[rt] = 0;
	}
}

void update(int l, int r, ll v, int L, int R, int rt) {
	if (l <= L && r >= R) {
		sum[rt] += (getv(R + 1) - getv(L)) * v;
		lazy[rt] += v;
		return;
	}
	push_down(rt, L, R);
	int mid = (L + R) >> 1;
	if (l <= mid)
		update(l, r, v, Lson);
	if (r > mid)
		update(l, r, v, Rson);
	push_up(rt);
}

int query(int l, int r, ll k, int L, int R, int rt) {
	if (L == R) {
		int ti = sum[rt] / (getv(R + 1) - getv(L));
		return getv(L) + (k - 1) / ti;
	}
	push_down(rt, L, R);
	int mid = (L + R) >> 1;
	if (sum[lson] >= k)
		return query(l, r, k, Lson);
	else
		return query(l, r, k - sum[lson], Rson);
}

int x[N], y[N];
int get_id(int v) {
	return lower_bound(des.begin(), des.end(), v) - des.begin() + 1;
}
int main() {
	int n;
	scanf("%d", &n);
	int m1, m2, a1, b1, a2, b2, c1, c2;
	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);
	q[1].l = min(x[1], y[1]) + 1;
	q[1].r = max(x[1], y[1]) + 1;
	if (n >= 2) {
		q[2].l = min(x[2], y[2]) + 1;
		q[2].r = max(x[2], y[2]) + 1;
	}
	for (int i = 3; i <= n; i++) {
		x[i] = (a1 * 1ll * x[i - 1] + b1 * 1ll * x[i - 2] + c1) % m1;
		y[i] = (a2 * 1ll * y[i - 1] + b2 * 1ll * y[i - 2] + c2) % m2;
		q[i].l = min(x[i], y[i]) + 1;
		q[i].r = max(x[i], y[i]) + 1;
	}
	for (int i = 1; i <= n; i++) {
		des.push_back(q[i].l);
		des.push_back(q[i].r + 1);
		dbg(i, q[i].l, q[i].r);
	}
	sort(des.begin(), des.end());
	des.erase(unique(des.begin(), des.end()), des.end());
	build(1, des.size(), 1);
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		 sum += q[i].r - q[i].l + 1;
		 int L = get_id(q[i].l), R = get_id(q[i].r + 1);
		 update(L, R - 1, 1, 1, des.size(), 1);
		 int ret = query(1, des.size(), (sum + 1) / 2, 1, des.size(), 1);
		 printf("%d\n", ret);
	}
	return 0;
}

0%