ctmm3M - Online C++ Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr int N = 1e5 + 1, GC = 36, B = 320;

int id[N], gc = 0;

struct Group {
    int len, sz, BS, BC;

    struct Node {
        int l, r;
        ll val;

        Node() = default;
        Node(ll _val) : val(_val) {}

        inline void assign(int _l, int _r) {
            l = _l;
            r = _r;
        }

        inline bool operator<(const Node &e) const { return val < e.val; }
    } rlist[N];

    struct Block {
        int lo, hi, lb, rb;
        ll lz;

        Block() = default;
        Block(int _rb) : rb(_rb) {}

        inline bool operator<(const Block &b) const { return rb < b.rb; }
    } blk[B];

    Group() = default;

    inline void init() {
        BS = sqrt(sz);
        BC = (sz - 1) / BS + 1;
        for (int i = 1; i <= BC; ++i) {
            blk[i].lo = blk[i - 1].hi + 1;
            blk[i].hi = i * BS;
        }
        blk[BC].hi = sz;
        for (int i = 1; i <= BC; ++i) {
            blk[i].lb = rlist[blk[i].lo].l;
            blk[i].rb = rlist[blk[i].hi].r;
        }
    }

    inline void modify(int p, int ql, int qr, int v) {
        for (int i = blk[p].lo; i <= blk[p].hi; ++i) {
            if (rlist[i].l > qr || rlist[i].r < ql) continue;
            rlist[i].val += (ll)(min(rlist[i].r, qr) - max(rlist[i].l, ql) + 1) * v;
        }
        sort(rlist + blk[p].lo, rlist + blk[p].hi + 1);
    }

    inline int count(int p, bool all, int ql, int qr, int v) {
        if (all) return upper_bound(rlist + blk[p].lo, rlist + blk[p].hi + 1, Node((ll)v - blk[p].lz)) - rlist - blk[p].lo;
        int res = 0;
        for (int i = blk[p].lo; i <= blk[p].hi; ++i) res += (ql <= rlist[i].l && rlist[i].r <= qr && rlist[i].val + blk[p].lz <= v);
        return res;
    }

    inline void update(int ql, int qr, int v) {
        int i = lower_bound(blk + 1, blk + BC + 1, Block(ql)) - blk;
        if (i > BC) return;
        if (blk[i].lb <= ql && qr <= blk[i].rb) {
            if (blk[i].lb == ql && qr == blk[i].rb) blk[i].lz += (ll)v * len;
            else modify(i, ql, qr, v);
            return;
        }
        if (blk[i].lb < ql) {
            modify(i, ql, blk[i].rb, v);
            ++i;
        }
        while (i <= BC && blk[i].rb <= qr) blk[i++].lz += (ll)v * len;
        if (i > BC) return;
        if (blk[i].lb <= qr) modify(i, blk[i].lb, qr, v);
    }

    inline int query(int ql, int qr, int v) {
        int i = lower_bound(blk + 1, blk + BC + 1, Block(ql)) - blk;
        if (i > BC) return 0;
        if (blk[i].lb <= ql && qr <= blk[i].rb) {
            if (blk[i].lb == ql && qr == blk[i].rb) return count(i, true, 0, 0, v);
            return count(i, false, ql, qr, v);
        }
        int res = 0;
        if (blk[i].lb < ql) {
            res += count(i, false, ql, blk[i].rb, v);
            ++i;
        }
        while (i <= BC && blk[i].rb <= qr) res += count(i++, true, 0, 0, v);
        if (i > BC) return res;
        if (blk[i].lb <= qr) res += count(i, false, blk[i].lb, qr, v);
        return res;
    }
} grp[GC];

void build(int l, int r) {
    const int len = r - l + 1;
    int &lid = id[len];
    if (!lid) {
        lid = ++gc;
        grp[gc].len = len;
    }
    grp[lid].rlist[++grp[lid].sz].assign(l, r);
    if (l == r) return;
    const int mid = l + r >> 1;
    build(l, mid);
    build(mid + 1, r);
}

int main() {
    int n, m, op, l, r, a;
    scanf("%d %d", &n, &m);
    build(1, n);
    for (int i = 1; i <= gc; ++i) grp[i].init();
    while (m--) {
        scanf("%d %d %d %d", &op, &l, &r, &a);
        if (op == 1) for (int i = 1; i <= gc; ++i) grp[i].update(l, r, a);
        else {
            int res = 0;
            for (int i = 1; i <= gc; ++i) res += grp[i].query(l, r, a);
            printf("%d\n", res);
        }
    }
}