我的思路:先离散化坐标,做法就是把每一个区间的右端点 + 1,然后排序后离散化。建一颗线段树,
线段树维护的信息:sum[](维护的是这个节点所映射的原始区间里面的数字出现的总次数) len[](记录的是这个节点所映射的原始区间的长度)
对于每一个加入的区间,离散化成两个点,然后区间修改。修改的时候采用lazy标记,找到所修改的区间后就让sum + len[o],再修改lazy标记
查询中位数的时候,让k=(总数 + 1)/ 2 ,查询第k小的数。(我考虑到叶子节点所映射的区间每一个数出现的频数相等才采用下面的查询方法)
但是,这份代码通过的样例是0.00%,我也很奇怪。之后对拍标答也没发现哪里有问题。
请求各位大佬可以帮我这个弱鸡看看
#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
const int maxn = 4e5 + 5;
typedef long long ll;
ll L[maxn], R[maxn];
ll tot[maxn * 2];
ll X[maxn], Y[maxn];
ll A1, B1, C1, M1, A2, B2, C2, M2;
ll sum[maxn << 3], lazy[maxn << 3], len[maxn << 3];///sum维护的是每一个节点所对应的区间映射的区间出现的次数
///len记录的是每一个节点所对应的区间长度
void build(int o, int l, int r){
if(l == r){
len[o] = tot[r + 1] - tot[l];
return ;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
len[o] = len[ls] + len[rs];
}
void Up(int o){
sum[o] = sum[ls] + sum[rs];
}
void pushdown(int o){
sum[ls] += len[ls] * lazy[o];
sum[rs] += len[rs] * lazy[o];
lazy[ls] += lazy[o];
lazy[rs] += lazy[o];
lazy[o] = 0;
}
void Update(int o, int l, int r, int x, int y){
if(l >= x && y >= r){
sum[o] += len[o];
lazy[o] ++;
return ;
}
if(lazy[o]) pushdown(o);
int mid = (l + r) >> 1;
if(mid >= x) Update(ls, l, mid, x, y);
if(y > mid) Update(rs, mid + 1, r, x, y);
Up(o);
}
int ans, k;
void query(int o, int l, int r){
if(l == r){
if(sum[o] >= k){
ans = tot[l] + (k - 1) / (sum[o] / len[o]);
}
else k -= sum[o];
return ;
}
if(lazy[o]) pushdown(o);
int mid = (l + r) >> 1;
if(sum[ls] < k) {
k -= sum[ls];
query(rs, mid + 1, r);
}
else query(ls, l, mid);
}
int main(){
int n;
scanf("%d", &n);
scanf("%lld%lld%lld%lld%lld%lld", &X[1], &X[2], &A1, &B1, &C1, &M1);
scanf("%lld%lld%lld%lld%lld%lld", &Y[1], &Y[2], &A2, &B2, &C2, &M2);
L[1] = min(X[1], Y[1]) + 1; L[2] = min(X[2], Y[2]) + 1;
R[1] = max(X[1], Y[1]) + 1; R[2] = max(X[2], Y[2]) + 1;
int Len = 0;
tot[++Len] = L[1]; tot[++Len] = L[2];
tot[++Len] = R[1] + 1; tot[++Len] = R[2] + 1;
for(int i = 3; i <= n; i++){
X[i] = ((A1 * X[i - 1]) % M1 + (B1 * X[i - 2]) % M1 + C1) % M1;
Y[i] = ((A2 * Y[i - 1]) % M2 + (B2 * Y[i - 2]) % M2 + C2) % M2;
L[i] = min(X[i], Y[i]) + 1;
R[i] = max(X[i], Y[i]) + 1;
tot[++Len] = L[i]; tot[++Len] = R[i] + 1;
}
sort(tot + 1, tot + Len +1);
int m = unique(tot + 1, tot + Len + 1) - (tot + 1);
m--;
build(1, 1, m);
ll num = 0;
for(int i = 1; i <= n; i++){
int x = lower_bound(tot + 1, tot + m + 2, L[i]) - tot;
int y = lower_bound(tot + 1, tot + m + 2, R[i] + 1) - tot;
Update(1, 1, m, x, y - 1);
num += (tot[y] - tot[x]);
k = (num + 1) / 2;
query(1, 1, m);
printf("%d\n", ans);
}
return 0;
}
全部评论
(1) 回帖