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