【BZOJ3110】【LG3332】[ZJOI2013]K大数查询

题面

题解

和普通的整体分治差不多

用线段树维护一下每个查询区间内大于每次二分的值\(mid\)的值即可

然后再按套路做就行了

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();

    if (ch == '-') w = -1 , ch = getchar();

    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

    return w * data;

}

typedef long long ll;

const int MAX_N = 50005;

#define lson (o << 1)

#define rson (o << 1 | 1)

struct SGT {

    bool clr; int tag; ll val;

    void clear() { clr = 0, tag = val = 0; }

} t[MAX_N << 2];

int N, M, ans[MAX_N];

void puttag(int o, int l, int r, int w) {

    t[o].val += 1ll * w * (r - l + 1);

    t[o].tag += w;

}

void clear(int o) {

    if (t[o].clr) {

        t[lson].clear(), t[rson].clear();

        t[lson].clr = t[rson].clr = 1;

        t[o].clr = 0;

    }

}

void pushdown(int o, int l, int r) {

    if (l == r) return ;

    int mid = (l + r) >> 1;

    clear(o);

    puttag(lson, l, mid, t[o].tag);

    puttag(rson, mid + 1, r, t[o].tag);

    t[o].tag = 0;

}

void modify(int o, int l, int r, int ql, int qr) {

    if (ql <= l && r <= qr) return (void)puttag(o, l, r, 1);

    pushdown(o, l, r);

    int mid = (l + r) >> 1;

    if (ql <= mid) modify(lson, l, mid, ql, qr);

    if (qr > mid) modify(rson, mid + 1, r, ql, qr);

    t[o].val = t[lson].val + t[rson].val;

}

ll query(int o, int l, int r, int ql, int qr) {

    pushdown(o, l, r);

    if (ql <= l && r <= qr) return t[o].val;

    int mid = (l + r) >> 1; ll res = 0;

    if (ql <= mid) res += query(lson, l, mid, ql, qr);

    if (qr > mid) res += query(rson, mid + 1, r, ql, qr);

    return res;

}

struct Query { int op, x, y; ll z; } q[MAX_N], lq[MAX_N], rq[MAX_N];

void Div(int lval, int rval, int st, int ed) {

    if (st > ed) return ;

    if (lval == rval) {

        for (int i = st; i <= ed; i++)

            if (q[i].op != 0) ans[q[i].op] = lval;

        return ;

    }

    int mid = (lval + rval) >> 1;

    int lt = 0, rt = 0;

    for (int i = st; i <= ed; i++) {

        if (q[i].op == 0) {

            if (q[i].z <= mid) lq[++lt] = q[i];

            else {

                rq[++rt] = q[i];

                modify(1, 1, N, q[i].x, q[i].y);

            }

        } else {

            ll res = query(1, 1, N, q[i].x, q[i].y);

            if (res >= q[i].z) rq[++rt] = q[i];

            else q[i].z -= res, lq[++lt] = q[i];

        }

    }

    for (int i = 1; i <= lt; i++) q[i + st - 1] = lq[i];

    for (int i = 1; i <= rt; i++) q[i + lt + st - 1] = rq[i];

    t[1].clear(); t[1].clr = 1;

    Div(lval, mid, st, st + lt - 1);

    Div(mid + 1, rval, st + lt, ed);

}

int main () {

    int tot = 0;

    N = gi(), M = gi();

    for (int i = 1; i <= M; i++) {

        q[i].op = gi() - 1;

        q[i].x = gi(), q[i].y = gi(), q[i].z = gi();

        if (q[i].op) q[i].op = ++tot;

    }

    Div(-N, N, 1, M);

    for (int i = 1; i <= tot; i++) printf("%d\n", ans[i]);

    return 0;

}

巴特西

【BZOJ3110】【LG3332】[ZJOI2013]K大数查询

【BZOJ3110】【LG3332】[ZJOI2013]K大数查询

题面

题解

最新文章

热门文章