2019牛客暑期多校训练营(第七场)
Find the median
题意: 先把输入处理一下，没啥问题吧。处理完后应该相当于每次在一个集合里面加入l,r之间所有的数，问中位数是多少。
题解： 这题很有意思，离散化+线段树 就能做，就相当于在线段树上求第sum/2个数在哪。比较朴素的就是先把所有的l,r保存下来，然后把他离散化，然后对离散化后的值做插入删除操作，我根据线段树动态开点的操作，写了个在线段树上直接离散化的操作，有点像把动态开点和离散化结合起来的感觉。
总体来说：就是需要哪个区间我就把线段树的下一个节点开什么样的l,r，不一定是刚好分一半。这样写很容易被卡掉，因为可能退化到$n^2$的复杂度。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
123
124
125
126
127
128
129
130
131
132
133
134
135
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
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;
clock_t prostart = clock();
void f() {
freopen("../data.in", "r", stdin);
}
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) { //需要什么点，开什么点
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;
}