#include using namespace std; #define int long long template struct SegmentTree{ using Func = function; int size; vector seg; const Func merge; const Monoid def; SegmentTree(int n, Monoid d, const Func f): merge(f), def(d){ for(size = 1; size <= n; size <<= 1); seg.assign(size*2, def); } Monoid& operator[] (int i) { return seg[i+size]; }; void build(){ for(int i = size-1;i >= 0;i--) seg[i] = merge(seg[i*2], seg[i*2+1]); } void update(int i, Monoid val){ seg[i += size] = val; while(i >>= 1) seg[i] = merge(seg[i*2], seg[i*2+1]); } void add(int i, Monoid val){ update(i, val+seg[i+size]); } Monoid get(int a, int b){ Monoid l = def, r = def; for(a += size, b += size; a < b; a >>= 1, b >>= 1){ if(a & 1) l = merge(l, seg[a++]); if(b & 1) r = merge(r, seg[--b]); } return merge(l, r); } }; int ans[100010] = {}; int ll[100010], rr[100010]; signed main(){ int n, q; cin >> n >> q; typedef pair P; SegmentTree

seg(n, {0, 0}, [](P a, P b){ return make_pair(a.first + b.first, a.second + b.second); }); vector

vec; for(int i = 0;i < n;i++){ int a; cin >> a; seg[i] = {a, 1}; vec.push_back({a, i}); } seg.build(); sort(vec.begin(), vec.end()); priority_queue, greater

> que; for(int i = 0;i < q;i++){ int a, x; cin >> a >> ll[i] >> rr[i] >> x; ll[i]--; que.push({x, i}); } int lp = 0; vec.push_back({1000000007, 0}); while(!que.empty()){ int idx = que.top().second; int x = que.top().first; int l = ll[idx]; int r = rr[idx]; que.pop(); while(vec[lp].first <= x){ seg.update(vec[lp].second, {0, 0}); lp++; } auto a = seg.get(l, r); ans[idx] = a.first - a.second*x; } for(int i = 0;i < q;i++){ cout << ans[i] << endl; } return 0; }