#pragma GCC optimize("Ofast") #include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <cstdio> #include <ctime> #include <assert.h> #include <chrono> #include <random> #include <numeric> #include <set> #include <deque> #include <stack> #include <sstream> #include <utility> #include <cstring> #include <unordered_map> #include <unordered_set> #include <tuple> #include <array> #include <bitset> using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } inline double time() { return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9; } // 1-indexed template<typename T> struct BIT{ int n; vector<T> bit; BIT(int n_=0):n(n_),bit(n+1){} T sum(int i){ T res=0; for(;i>0;i-=(i&-i))res+=bit[i]; return res; } void add(int i,T a){ if(i==0)return; for(;i<=n;i+=(i&-i)){bit[i]+=a;} } int lower_bound(T k){ // k<=sum(res) if(k<=0)return 0; int res=0,i=1; while((i<<1)<=n)i<<=1; for(;i;i>>=1){ if(res+i<=n&&bit[res+i]<k)k-=bit[res+=i]; } return res+1; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,q; cin >> n >> q; BIT<ll> bit(n),cnt(n); vector<pair<pair<int,int>,pair<int,int>>> v; for(int i=0;i<n;i++){ int a; cin >> a; v.push_back({{a,i+1},{-1,-1}}); } vector<ll> res(q); for(int i=0;i<q;i++){ int l,r,x; cin >> l >> r >> x; v.push_back({{x,i},{l,r}}); } sort(v.begin(), v.end()); for(auto &p:v){ if(p.second.first == -1){ int idx = p.first.second; int a = p.first.first; bit.add(idx, a); cnt.add(idx, 1); } else{ int idx = p.first.second; ll cn = cnt.sum(p.second.second) - cnt.sum(p.second.first-1); ll su = bit.sum(p.second.second) - bit.sum(p.second.first-1); res[idx] = su + (ll)(p.second.second-p.second.first+1-cn)*(ll)p.first.first; } } for(int i=0;i<q;i++){ cout << res[i] << "\n"; } }