题目链接: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;
}