fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. constexpr int N = 1e5 + 1, TC = 36, B = 350;
  6.  
  7. int id[N], tc = 0;
  8.  
  9. struct Group {
  10.     int len, sz, BS, BC;
  11.  
  12.     struct Element {
  13.         int l, r;
  14.         ll val;
  15.  
  16.         Element() = default;
  17.         Element(ll _val) : val(_val) {}
  18.  
  19.         inline void assign(int _l, int _r) {
  20.             l = _l;
  21.             r = _r;
  22.         }
  23.  
  24.         inline bool operator<(const Element &e) const { return val < e.val; }
  25.     } rlist[N];
  26.  
  27.     struct Block {
  28.         int lo, hi, lmax, rmax;
  29.         ll lz;
  30.  
  31.         Block() = default;
  32.         Block(int _rmax) : rmax(_rmax) {}
  33.  
  34.         inline bool operator<(const Block &b) const { return rmax < b.rmax; }
  35.     } blk[B];
  36.  
  37.     Group() = default;
  38.  
  39.     inline void init() {
  40.         BS = sqrt(sz);
  41.         BC = (sz - 1) / BS + 1;
  42.         for (int i = 1; i <= BC; ++i) {
  43.             blk[i].lo = blk[i - 1].hi + 1;
  44.             blk[i].hi = i * BS;
  45.         }
  46.         blk[BC].hi = sz;
  47.         for (int i = 1; i <= BC; ++i) {
  48.             blk[i].lmax = rlist[blk[i].lo].l;
  49.             blk[i].rmax = rlist[blk[i].hi].r;
  50.         }
  51.     }
  52.  
  53.     inline void modify(int p, int ql, int qr, int v) {
  54.         for (int i = blk[p].lo; i <= blk[p].hi; ++i) {
  55.             if (rlist[i].l > qr || rlist[i].r < ql) continue;
  56.             rlist[i].val += (ll)(min(rlist[i].r, qr) - max(rlist[i].l, ql) + 1) * v;
  57.         }
  58.         sort(rlist + blk[p].lo, rlist + blk[p].hi + 1);
  59.     }
  60.  
  61.     inline int count(int p, bool all, int ql, int qr, int v) {
  62.         if (all) return upper_bound(rlist + blk[p].lo, rlist + blk[p].hi + 1, Element((ll)v - blk[p].lz)) - rlist - blk[p].lo;
  63.         int res = 0;
  64.         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);
  65.         return res;
  66.     }
  67.  
  68.     inline void update(int ql, int qr, int v) {
  69.         int i = lower_bound(blk + 1, blk + BC + 1, Block(ql)) - blk;
  70.         if (i > BC) return;
  71.         if (blk[i].lmax <= ql && qr <= blk[i].rmax) {
  72.             if (blk[i].lmax == ql && qr == blk[i].rmax) blk[i].lz += (ll)v * len;
  73.             else modify(i, ql, qr, v);
  74.             return;
  75.         }
  76.         if (blk[i].lmax < ql) {
  77.             modify(i, ql, blk[i].rmax, v);
  78.             ++i;
  79.         }
  80.         while (i <= BC && blk[i].rmax <= qr) blk[i++].lz += (ll)v * len;
  81.         if (i > BC) return;
  82.         if (blk[i].lmax <= qr) modify(i, blk[i].lmax, qr, v);
  83.     }
  84.  
  85.     inline int query(int ql, int qr, int v) {
  86.         int i = lower_bound(blk + 1, blk + BC + 1, Block(ql)) - blk;
  87.         if (i > BC) return 0;
  88.         if (blk[i].lmax <= ql && qr <= blk[i].rmax) {
  89.             if (blk[i].lmax == ql && qr == blk[i].rmax) return count(i, true, 0, 0, v);
  90.             return count(i, false, ql, qr, v);
  91.         }
  92.         int res = 0;
  93.         if (blk[i].lmax < ql) {
  94.             res += count(i, false, ql, blk[i].rmax, v);
  95.             ++i;
  96.         }
  97.         while (i <= BC && blk[i].rmax <= qr) res += count(i++, true, 0, 0, v);
  98.         if (i > BC) return res;
  99.         if (blk[i].lmax <= qr) res += count(i, false, blk[i].lmax, qr, v);
  100.         return res;
  101.     }
  102. } grp[TC];
  103.  
  104. void build(int l, int r) {
  105.     const int len = r - l + 1;
  106.     int &lid = id[len];
  107.     if (!lid) {
  108.         lid = ++tc;
  109.         grp[tc].len = len;
  110.     }
  111.     grp[lid].rlist[++grp[lid].sz].assign(l, r);
  112.     if (l == r) return;
  113.     const int mid = l + r >> 1;
  114.     build(l, mid);
  115.     build(mid + 1, r);
  116. }
  117.  
  118. int main() {
  119.     int n, m, op, l, r, a;
  120.     scanf("%d %d", &n, &m);
  121.     build(1, n);
  122.     for (int i = 1; i <= tc; ++i) grp[i].init();
  123.     while (m--) {
  124.         scanf("%d %d %d %d", &op, &l, &r, &a);
  125.         if (op == 1) for (int i = 1; i <= tc; ++i) grp[i].update(l, r, a);
  126.         else {
  127.             int res = 0;
  128.             for (int i = 1; i <= tc; ++i) res += grp[i].query(l, r, a);
  129.             printf("%d\n", res);
  130.         }
  131.     }
  132. }
Success #stdin #stdout 0.01s 5804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OlAuC1
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!