2019 우 객 여름 다 교 훈련소 (7 차 전) E Find the median

2019 우 객 여름 다 교 훈련소 (7 차 전) 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("*********
");
#define debug(x) cout<


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
", querry(0, (S+1) / 2));
    }
    return 0;
}