Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- class Fenwick {
- private:
- vector<ll> val;
- public:
- Fenwick(int n) : val(n+1, 0) {}
- // Adds v to index i
- void add(int i, ll v) {
- for (++i; i < val.size(); i += i & -i) {
- val[i] += v;
- }
- }
- // Calculates prefix sum up to index i
- ll get(int i) {
- ll res = 0;
- for (++i; i > 0; i -= i & -i) {
- res += val[i];
- }
- return res;
- }
- ll get(int a, int b) { return get(b) - get(a-1); }
- };
- // Segment tree for range minimum and addition.
- class SegTree {
- private:
- const ll NEUT = 4 * (ll)1e18;
- vector<ll> seg, tag;
- int h = 1;
- void apply(int i, ll v) {
- seg[i] += v;
- if (i < h) tag[i] += v;
- }
- void push(int i) {
- if (tag[i] == 0) return;
- apply(2*i, tag[i]);
- apply(2*i+1, tag[i]);
- tag[i] = 0;
- }
- ll combine(ll a, ll b) { return min(a, b); }
- ll recGet(int a, int b, int i, int ia, int ib) {
- if (ib <= a || b <= ia) return NEUT;
- if (a <= ia && ib <= b) return seg[i];
- push(i);
- int im = (ia + ib) >> 1;
- return combine(
- recGet(a, b, 2*i, ia, im),
- recGet(a, b, 2*i+1, im, ib));
- }
- void recApply(int a, int b, ll v, int i, int ia, int ib) {
- if (ib <= a || b <= ia) return;
- if (a <= ia && ib <= b) apply(i, v);
- else {
- push(i);
- int im = (ia + ib) >> 1;
- recApply(a, b, v, 2*i, ia, im);
- recApply(a, b, v, 2*i+1, im, ib);
- seg[i] = combine(seg[2*i], seg[2*i+1]);
- }
- }
- int recFind(int a, int b, ll v, int i, int ia, int ib) {
- if (seg[i] > v) return b;
- if (b <= ia || ib <= a) return b;
- if (ib == ia + 1) return ia;
- push(i);
- int im = (ia + ib) >> 1;
- int off = recFind(a, b, v, 2*i, ia, im);
- if (off < b) return off;
- else return recFind(a, b, v, 2*i+1, im, ib);
- }
- public:
- SegTree(int n) {
- while(h < n) h *= 2;
- seg.resize(2*h, 0);
- tag.resize(h, 0);
- }
- ll rangeMin(int a, int b) { return recGet(a, b+1, 1, 0, h); }
- void rangeAdd(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
- int findNext(int a, int b, ll v) { return recFind(a, b+1, v, 1, 0, h); }
- };
- struct SegTreeBeats {
- private:
- const ll INF = 4 * (ll)1e18;
- vector<ll> add, cap;
- int h = 1;
- void apply(int i, ll a, ll c) {
- cap[i] = min(cap[i] + a, c);
- if (i < h) add[i] += a;
- }
- void push(int i) {
- apply(2*i, add[i], cap[i]);
- apply(2*i+1, add[i], cap[i]);
- add[i] = 0;
- cap[i] = INF;
- }
- void recAdd(int a, int b, ll v, int i, int ia, int ib) {
- if (ib <= a || b <= ia) return;
- else if (a <= ia && ib <= b) apply(i, v, INF);
- else {
- push(i);
- int im = (ia + ib) >> 1;
- recAdd(a, b, v, 2*i, ia, im);
- recAdd(a, b, v, 2*i+1, im, ib);
- }
- }
- ll recMax(int a, int b, int i, int ia, int ib) {
- if (ib <= a || b <= ia) return -INF;
- if (a <= ia && ib <= b) return cap[i];
- push(i);
- int im = (ia + ib) >> 1;
- return max(recMax(a, b, 2*i, ia, im), recMax(a, b, 2*i+1, im, ib));
- }
- public:
- SegTreeBeats(int n) {
- while(h < n) h <<= 1;
- add.resize(h, 0);
- cap.resize(2*h, 0);
- }
- void rangeAdd(int a, int b, ll v) { recAdd(a, b+1, v, 1, 0, h); apply(1, 0, 0); }
- ll get(int i) { return recMax(i, i+1, 1, 0, h); }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n, m, q;
- cin >> n >> m >> q;
- SegTreeBeats cur(n);
- Fenwick tot(n+1);
- vector<int> res;
- vector<vector<pair<ll, int>>> qs(n);
- vector<array<ll, 5>> ops(q);
- for (int qi = 0; qi < q; ++qi) {
- cin >> ops[qi][0];
- ll a, b;
- cin >> a >> b;
- --a; --b;
- ops[qi][1] = a; ops[qi][2] = b;
- if (ops[qi][0] == 1) {
- ll c, k;
- cin >> c >> k;
- ops[qi][3] = c; ops[qi][4] = k;
- cur.rangeAdd(a, b, -k);
- tot.add(a, k);
- tot.add(b+1, -k);
- } else if (ops[qi][0] == 2) {
- ll k;
- cin >> k;
- ops[qi][3] = k;
- cur.rangeAdd(a, b, k);
- } else if (ops[qi][0] == 3) {
- ++b;
- ll v = -cur.get(a);
- int ind = res.size();
- res.emplace_back(0);
- if (v >= b) qs[a].emplace_back(tot.get(a) - (v - b), ind);
- }
- }
- const ll INF = 1e18;
- SegTree groups(n);
- vector<int> inds(n, 0);
- for (int i = 0; i < n; ++i) {
- if (qs[i].empty()) {
- groups.rangeAdd(i, i, INF);
- } else {
- sort(qs[i].begin(), qs[i].end());
- groups.rangeAdd(i, i, qs[i][0].first);
- }
- }
- for (int qi = 0; qi < q; ++qi) {
- int t = ops[qi][0];
- if (t == 1) {
- ll a = ops[qi][1]; ll b = ops[qi][2];
- ll c = ops[qi][3]; ll k = ops[qi][4];
- groups.rangeAdd(a, b, -k);
- while(true) {
- int j = groups.findNext(0, n-1, 0);
- if (j == n) break;
- res[qs[j][inds[j]].second] = c;
- ++inds[j];
- if (inds[j] >= qs[j].size()) {
- groups.rangeAdd(j, j, INF);
- } else {
- groups.rangeAdd(j, j, qs[j][inds[j]].first - qs[j][inds[j] - 1].first);
- }
- }
- }
- }
- for (auto c : res) cout << c << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement