2019牛客暑期多校训练营(第七场) E Find the median

2019牛客暑期多校训练营(第七场)

Find the median

题意: 先把输入处理一下，没啥问题吧。处理完后应该相当于每次在一个集合里面加入

l,r

之间所有的数，问中位数是多少。

题解： 这题很有意思，离散化+线段树 就能做，就相当于在线段树上求第

sum/2

个数在哪。比较朴素的就是先把所有的

l,r

保存下来，然后把他离散化，然后对离散化后的值做插入删除操作，我根据线段树动态开点的操作，写了个在线段树上直接离散化的操作，有点像把动态开点和离散化结合起来的感觉。

总体来说：就是需要哪个区间我就把线段树的下一个节点开什么样的

l,r

，不一定是刚好分一半。这样写很容易被卡掉，因为可能退化到 n 2 n^2 n2的复杂度。

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;


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;
#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

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;
}