P5063 [Ynoi2014] 置身天上之森

#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 1e5 + 9;
constexpr int sqn = 350;

struct _6th_island {
  int n, m, B, cnt;

  struct Rakishu {
    int l, r;
    LL v;
    bool operator < (const Rakishu &rhs) const {
      return v < rhs.v;
    }
  } a[N];

  struct island {
    int L, R, s, t;
    LL x;
    bool operator < (const island &rhs) const {
      return t < rhs.t;
    }
  } b[sqn];

  void init () {
    B = sqrt(n);
    cnt = (n + B - 1) / B;
    L (i, 1, cnt) {
      b[i].L = b[i - 1].R + 1;
      b[i].R = min(n, i * B);
      b[i].s = a[b[i].L].l;
      b[i].t = a[b[i].R].r;
    }
  }

  void bf_mdy (int p, int l, int r, int x) {
    L (i, b[p].L, b[p].R) {
      if (a[i].r < l || a[i].l > r) {
        continue;
      }
      a[i].v += (LL)x * (min(r, a[i].r) - max(l, a[i].l) + 1);
    }
    stable_sort(a + b[p].L, a + b[p].R + 1);
  }

  int bf_qry (int p, int l, int r, LL x) {
    x -= b[p].x;
    int ret = 0;
    L (i, b[p].L, b[p].R) {
      ret += (l <= a[i].l && a[i].r <= r && a[i].v <= x);
    }
    return ret;
  }

  int qry_all (int p, LL x) {
    x -= b[p].x;
    return x >= a[b[p].R].v ? b[p].R - b[p].L + 1 : (x < a[b[p].L].v ? 0 : upper_bound(a + b[p].L, a + b[p].R + 1, (Rakishu){0, 0, x}) - a - b[p].L);
  }

  void mdy (int l, int r, int x) {
    int p = lower_bound(b + 1, b + cnt + 1, (island){0, 0, 0, l, 0}) - b;
    if (b[p].s <= l && r <= b[p].t) {
      if (b[p].s == l && b[p].t == r) {
        b[p].x += x * (LL)m;
        return;
      }
      bf_mdy(p, l, r, x);
      return;
    }
    if (b[p].s < l) {
      bf_mdy(p, l, r, x);
      p += 1;
    }
    while (p <= cnt && b[p].t <= r) {
      b[p].x += x * (LL)m;
      ++p;
    }
    if (p <= cnt && b[p].s <= r) {
      bf_mdy(p, l, r, x);
    }
  }

  int qry (int l, int r, LL x) {
    int p = lower_bound(b + 1, b + cnt + 1, (island){0, 0, 0, l, 0}) - b;
    if (p > cnt) {
      return 0;
    }
    if (b[p].s <= l && r <= b[p].t) {
      if (b[p].s == l && b[p].t == r) {
        return qry_all(p, x);
      }
      return bf_qry(p, l, r, x);
    }
    int ret = 0;
    if (b[p].s < l) {
      ret += bf_qry(p, l, r, x);
      p += 1;
    }
    while (p <= cnt && b[p].t <= r) {
      ret += qry_all(p, x);
      ++p;
    }
    if (p <= cnt && b[p].s <= r) {
      ret += bf_qry(p, l, r, x);
    }
    return ret;
  }
} kk[36];

int n, m, mp[N], tot;

void bld (int l, int r) {
  int x = r - l + 1;
  if (!mp[x]) {
    mp[x] = ++tot;
    kk[tot].m = x;
  }
  int id = mp[x];
  int y = ++kk[id].n;
  kk[id].a[y] = (_6th_island::Rakishu){l, r, 0};
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  bld(l, mid);
  bld(mid + 1, r);
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  bld(1, n);
  L (i, 1, tot) {
    kk[i].init();
  }
  while (m--) {
    int o, l, r, x;
    cin >> o >> l >> r >> x;
    if (o == 1) {
      L (i, 1, tot) {
        kk[i].mdy(l, r, x);
      }
    } else {
      int s = 0;
      L (i, 1, tot) {
        if (r - l + 1 >= kk[i].m) {
          s += kk[i].qry(l, r, x);
        }
      }
      cout << s << '\n';
    }
  }
}
// I love WHQ!