/* -*- coding: utf-8 -*- * * 877.cc: No.877 Range ReLU Query - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_E2 = 1 << 18; // = 262144 const int MAX_QN = 100000; const int MAX_M = MAX_N + MAX_QN; /* typedef */ typedef long long ll; struct Elm { ll a, b; Elm() {} Elm(ll _a, ll _b): a(_a), b(_b) {} Elm operator+(const Elm &e) const { return Elm(a + e.a, b + e.b); } }; template <typename T, const int MAX_E2> struct SegTreeSum { int n, e2; T nodes[MAX_E2], z; SegTreeSum() {} void init(int _n, T _z) { n = _n; z = _z; for (e2 = 1; e2 < n; e2 <<= 1); fill(nodes, nodes + MAX_E2, z); } T &get(int i) { return nodes[e2 - 1 + i]; } void set(int i, T v) { int j = e2 - 1 + i; nodes[j] = v; while (j > 0) { j = (j - 1) / 2; nodes[j] = nodes[j * 2 + 1] + nodes[j * 2 + 2]; } } void setall() { for (int j = e2 - 2; j >= 0; j--) nodes[j] = nodes[j * 2 + 1] + nodes[j * 2 + 2]; } T sum_range(int r0, int r1, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return z; if (r0 <= i0 && i1 <= r1) return nodes[k]; int im = (i0 + i1) / 2; T v0 = sum_range(r0, r1, k * 2 + 1, i0, im); T v1 = sum_range(r0, r1, k * 2 + 2, im, i1); return v0 + v1; } T sum_range(int r0, int r1) { return sum_range(r0, r1, 0, 0, e2); } }; struct Op { int c, l, r, x, i; Op() {} Op(int _c, int _l, int _r, int _x, int _i): c(_c), l(_l), r(_r), x(_x), i(_i) {} Op(int _x, int _i): c(0), l(0), r(0), x(_x), i(_i) {} bool operator<(const Op &o) const { return x < o.x || (x == o.x && c < o.c); } }; /* global variables */ Op ps[MAX_M]; SegTreeSum<Elm,MAX_E2> st; ll ans[MAX_N]; /* subroutines */ /* main */ int main() { int n, qn; scanf("%d%d", &n, &qn); int m = 0; for (int i = 0; i < n; i++) { int ai; scanf("%d", &ai); ps[m++] = Op(ai, i); } for (int i = 0; i < qn; i++) { int c, l, r, x; scanf("%d%d%d%d", &c, &l, &r, &x); l--; ps[m++] = Op(c, l, r, x, i); } sort(ps, ps + m); st.init(n, Elm(0, 0)); for (int i = m - 1; i >= 0; i--) { if (ps[i].c == 0) st.set(ps[i].i, Elm(ps[i].x, 1)); else { Elm e = st.sum_range(ps[i].l, ps[i].r); ans[ps[i].i] = e.a - e.b * ps[i].x; } } for (int i = 0; i < qn; i++) printf("%lld\n", ans[i]); return 0; }