题解：AT_joisc2021_c フードコート (Foodcourt)

· · 题解

整体二分好题。

首先这个离开操作完全不必要，每次查询时只需要加上离开的人数，然后在一共来的人数查询即可，这东西可以用一个树状数组维护一共来过的人数，一个线段树维护当前的人数，离开人数使两者作差即可，在输入询问时就可以处理到操作中。

然后是对所有操作整体二分，二分到某个操作时，如果那该操作加入的人正好刚好满足某一个询问，那么就是那个询问的答案，这里直接统计，因为后面继续分治时如果有更小的满足会自动覆盖掉。

理解代码应该更容易懂。

code

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define INF 1000000000000000000
using namespace std;

const int N = 3e5;

struct BIT {
    int c[N];

    inline void add (int x, int k) {
        for (; x < N; x += (x & -x)) c[x] += k;
    }

    inline int sum (int x) {
        int res = 0;
        for (; x; x -= (x & -x)) res += c[x];
        return res;
    }
} bit;

struct SegmentTree {
    int sum[N << 2], tag[N << 2], matag[N << 2];

    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid ((l + r) >> 1)

    inline int max (int a, int b) {
        return a > b ? a : b; 
    }

    inline void pushup (int p) {
        sum[p] = max (sum[ls], sum[rs]);
    }

    inline void push (int &x, int p) {
        x = max (x + tag[p], matag[p]);
    }

    inline void pushdown (int p) {
        push (sum[ls], p), push (sum[rs], p), push (matag[ls], p), push (matag[rs], p), tag[ls] += tag[p], tag[rs] += tag[p], matag[p] = tag[p] = 0;
    }

    void update (int p, int l, int r, int L, int R, int k) {
        if (L <= l and r <= R) return sum[p] = max (sum[p] + k, 0), tag[p] += k, matag[p] = max (matag[p] + k, 0), void ();
        pushdown (p);
        if (L <= mid) update (ls, l, mid, L, R, k);
        if (R > mid) update (rs, mid + 1, r, L, R, k);
        pushup (p);
    }

    int query (int p, int l, int r, int x) {
        if (l == r) return sum[p];
        return pushdown (p), (x <= mid ? query (ls, l, mid, x) : query (rs, mid + 1, r, x));
    }

    #undef ls
    #undef rs
    #undef mid
} seg; 

int n, m, q, len;

int ans[N], f[N];

struct Que {
    int t, x, k, type;
} que[N << 1];

inline bool cmp (Que a, Que b) {
    return a.x == b.x ? a.type < b.type : a.x < b.x;
} 

void solve (int l, int r, int L, int R) {
    int mid = (L + R) >> 1, now = 0; 
    vector <Que> ls, rs;
    for (int i = l; i <= r; i++)
        if (que[i].type)
            if (now >= que[i].k) ans[que[i].t] = mid, ls.pb (que[i]);
            else que[i].k -= now, rs.pb (que[i]);
        else 
            if (que[i].t <= mid) now += que[i].k, ls.pb (que[i]);
            else rs.pb (que[i]);
    int i = l; 
    for (Que x : ls) que[i++] = x;
    for (Que x : rs) que[i++] = x;
    if (L == R) return;
    solve (l, l + ls.size () - 1, L, mid), solve (l + ls.size (), r, mid + 1, R);
}

signed main () {
    ios :: sync_with_stdio (false), cin.tie (0), cout.tie (0), cin >> n >> m >> q;
    for (int i = 1, opt, l, r, x, y; i <= q; i++) {
        cin >> opt;
        if (opt == 1) cin >> l >> r >> x >> y, bit.add (l, y), bit.add (r + 1, -y), seg.update (1, 1, n, l, r, y), que[++len] = (Que) {i, l, y, 0}, que[++len] = (Que) {i, r + 1, -y, 0}, f[i] = x;
        if (opt == 2) cin >> l >> r >> x, seg.update (1, 1, n, l, r, -x);
        if (opt == 3) cin >> x >> y, que[++len] = (Que) {i, x, bit.sum (x) - seg.query (1, 1, n, x) + y, 1};
    } 
    que[++len] = (Que) {q + 1, 1, INF, 0}, sort (que + 1, que + 1 + len, cmp), solve (1, len, 1, q + 1);
    for (int i = 1; i <= q; i++) if (ans[i]) cout << (ans[i] < i ? f[ans[i]] : 0) << endl;
    return 0;
}