题目链接

题解

整体二分

Code

#include
    
     #define LL long long#define RG registerusing namespace std;inline int gi() {    RG int x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();    return f ? -x : x;}const int N = 50010;int n, m;#define ls (rt<<1)#define rs (rt<<1|1)LL t[N<<2], z[N<<2];inline void pushdown(int rt, int l, int r) {    if (z[rt]) {        int mid = (l + r) >> 1;        t[ls] += (mid-l+1)*z[rt]; t[rs] += (r-mid)*z[rt];        z[ls] += z[rt]; z[rs] += z[rt];        z[rt] = 0;    }    return;}inline void update(int rt, int l, int r, int L, int R, int k) {    if (L <= l && r <= R) {        z[rt] += k;        t[rt] += k*(r-l+1);        return ;    }    int mid = (l + r) >> 1;    pushdown(rt, l, r);    if (L <= mid)        update(ls, l, mid, L, R, k);    if (R > mid)        update(rs, mid+1, r, L, R, k);    t[rt] = t[ls]+t[rs];    return ;}inline LL query(int rt, int l, int r, int L, int R) {    if (L <= l && r <= R) return t[rt];    int mid = (l + r) >> 1;    LL s = 0;    pushdown(rt, l, r);    if (L <= mid)        s = query(ls, l, mid, L, R);    if (R > mid)        s += query(rs, mid+1, r, L, R);    t[rt] = t[ls]+t[rs];    return s;}struct Question {    int op, a, b, id;    LL c;}q[N], lq[N], rq[N];LL ans[N];void div(int l, int r, int st, int ed) {    if (st > ed) return ;    if (l == r) {        for (int i = st; i <= ed; i++)            if (q[i].op == 2)                ans[q[i].id] = l;        return ;    }    int mid = (l + r) >> 1, lt = 0, rt = 0;    for (int i = st; i <= ed; i++) {        if (q[i].op == 1) {            if (q[i].c <= mid)                lq[++lt] = q[i];            else update(1, 1, n, q[i].a, q[i].b, 1), rq[++rt] = q[i];        }        else {            LL s = query(1, 1, n, q[i].a, q[i].b);            if (s >= q[i].c) rq[++rt] = q[i];            else q[i].c -= s, lq[++lt] = q[i];        }    }    for (int i = st; i <= ed; i++)        if (q[i].op == 1 && q[i].c > mid) update(1, 1, n, q[i].a, q[i].b, -1);    for (int i = 1; i <= lt; i++)        q[st+i-1] = lq[i];    for (int i = 1; i <= rt; i++)        q[st+lt+i-1] = rq[i];    div(l, mid, st, st+lt-1); div(mid+1, r, st+lt, ed);    return ;}int main() {    n = gi(); m = gi();    int k = 0;    for (int i = 1; i <= m; i++) {        q[i].op = gi(), q[i].a = gi(), q[i].b = gi();        scanf("%lld", &q[i].c);        q[i].id = (q[i].op == 2) ? ++k : 0;    }    div(-n, n, 1, m);    for (int i = 1; i <= k; i++)        printf("%lld\n", ans[i]);    return 0;}