#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include using namespace std; // 型名の短縮 using ll = long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; template using priority_queue_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); const vi dx4 = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左) const vi dy4 = { 0, 1, 0, -1 }; const vi dx8 = { 1, 1, 0, -1, -1, -1, 0, 1 }; // 8 近傍 const vi dy8 = { 0, 1, 1, 1, 0, -1, -1, -1 }; const int INF = 1001001001; const ll INFL = 4004004004004004004LL; const double EPS = 1e-12; // 許容誤差に応じて調整 // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define distance (int)distance #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define YES(b) {cout << ((b) ? "YES\n" : "NO\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 // 汎用関数の定義 template inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v) --x; return v; } template inline vector& operator++(vector& v) { repea(x, v) ++x; return v; } // 手元環境(Visual Studio) #ifdef _MSC_VER #include "local.hpp" // 提出用(gcc) #else #define popcount (int)__builtin_popcount #define popcountll (int)__builtin_popcountll #define lsb __builtin_ctz #define lsbll __builtin_ctzll #define msb(n) (31 - __builtin_clz(n)) #define msbll(n) (63 - __builtin_clzll(n)) #define gcd __gcd #define dump(...) #define dumpel(v) #define input_from_file(f) #define output_to_file(f) #endif #endif // 折りたたみ用 //--------------AtCoder 専用-------------- #include using namespace atcoder; //using mint = modint1000000007; using mint = modint998244353; //using mint = modint; // mint::set_mod(m); istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } using vm = vector; using vvm = vector; using vvvm = vector; //---------------------------------------- //【ウェーブレット行列】 /* * Wavelet_matrix(vl a) : O(n log n log A) * 非負整数列 a で初期化する.(A = max(a) とおく.) * * ll get(int i) : O(log(max a)) * 昇順で i 番目の要素を返す. * * ll get(int l, int r, int i) : O(log A)) * a[l..r) の中で昇順で i 番目の要素を返す. * * int count(int l, int r, ll v) : O(log A) * a[l..r) に v が何個あるかを返す. * * int count(int l, int r, ll v0, ll v1) : O(log A) * a[l..r) の中で [v0..v1) に値をもつ要素の個数を返す. * * int position(ll v, int c) : O(log n log A) * 昇順で c 番目の v の位置を返す. * * frequency(int l, int r, int c, vector& freq) : O(min(r - l, A) log A) * a[l..r) の中で出現頻度降順に最大 c 個の要素と頻度の組のリストを freq に格納する. * * ll sum(int l, int r) : O(1) * a[l..r) の和を返す. * * ll sum(int l, int r, ll v0, ll v1) : O(log A) * a[l..r) の中で [v0..v1) に値をもつ要素の和を返す. * * intersection(int l1, int r1, int l2, int r2, vector>& freq) : O(min((r1 - l1) + (r2 - l2), A) log A) * a[l1..r1) と a[l2..r2) に共通する要素を求め, * その値とそれぞれにおける出現頻度の三つ組のリストを freq に格納する. */ class Wavelet_matrix { // 参考 : https://miti-7.hatenablog.com/entry/2018/04/28/152259 int n; // 要素数 int k; // msb 以下の桁数(1-indexed) vvb bs; // bs[j][i] : 第 j + 1 ビットについての安定ソート後の a[i] の第 j ビット vvvi bs_acc; // bs[b] : のビット b = 0, 1 それぞれの個数の累積和 vi num_zeros; // num_zeros[j] : bs[j] の 0 の個数 unordered_map id; // 値 → 安定ソートが終わったときの最左位置 vvl acc; // acc[j] : 第 j ビットについての安定ソート後の a の累積和 // a[0..r) に v が何個あるかを返す. int count_sub(int r, ll v) { // 一つも無ければすぐに 0 を返す. if (!id.count(v)) return 0; // 最上位ビットから順に見ていく repir(j, k - 1, 0) { // 注目ビットに応じて次の位置を求めていく. if (v & (1LL << j)) { r = num_zeros[j] + bs_acc[1][j][r]; } else { r = bs_acc[0][j][r]; } } return r - id[v]; } // a[l..r) の中で [0..v) に値をもつ要素の個数を返す. int count_rsub(int l, int r, ll v) { if (msbll(v) >= k) return r - l; int cnt = 0; repir(j, k - 1, 0) { if (v & (1LL << j)) { cnt += bs_acc[0][j][r] - bs_acc[0][j][l]; r = num_zeros[j] + bs_acc[1][j][r]; l = num_zeros[j] + bs_acc[1][j][l]; } else { r = bs_acc[0][j][r]; l = bs_acc[0][j][l]; } } return cnt; } // a[l..r) の中で [0..v) に値をもつ要素の和を返す. ll sum_rsub(int l, int r, ll v) { if (msbll(v) >= k) return acc[k][r] - acc[k][l]; ll res = 0; repir(j, k - 1, 0) { if (v & (1LL << j)) { res += acc[j][bs_acc[0][j][r]] - acc[j][bs_acc[0][j][l]]; r = num_zeros[j] + bs_acc[1][j][r]; l = num_zeros[j] + bs_acc[1][j][l]; } else { r = bs_acc[0][j][r]; l = bs_acc[0][j][l]; } } return res; } public: // 非負整数列 t で初期化する. Wavelet_matrix(const vl& t) : n(sz(t)), k(msbll(*max_element(all(t))) + 1), bs(k, vb(n)), bs_acc(2, vvi(k, vi(n + 1))), num_zeros(k), acc(k + 1, vl(n + 1)) { // verify : https://judge.yosupo.jp/problem/static_range_frequency // ビットと組にして安定ソートするためのリスト vector> bt(n); rep(i, n) bt[i].second = t[i]; // j : 注目ビット位置(上位ビットから順に見ていく) repir(j, k - 1, 0) { rep(i, n) { // 注目ビットが 1 か bs[j][i] = bt[i].first = (bt[i].second & (1LL << j)); // ビット 0, 1 それぞれの個数の累積和を求めておく. rep(b, 2) bs_acc[b][j][i + 1] = bs_acc[b][j][i]; if (bs[j][i]) { bs_acc[1][j][i + 1]++; } else { bs_acc[0][j][i + 1]++; num_zeros[j]++; } // 要素の累積和の計算 acc[j + 1][i + 1] = acc[j + 1][i] + bt[i].second; } // 注目ビットが 0 のものを左,1 のものを右に寄せる安定ソートを行う. stable_sort(all(bt), [](auto const& lhs, auto const& rhs) { return lhs.first < rhs.first; }); } rep(i, n) { // 値 → 安定ソートが終わったときの最左位置 if (!id.count(bt[i].second)) id[bt[i].second] = i; // 要素の累積和の計算 acc[0][i + 1] = acc[0][i] + bt[i].second; } } Wavelet_matrix() : n(0), k(0) {} // ダミー // 昇順で i 番目の要素を返す. ll get(int i) { ll res = 0; // 最上位ビットから順に見ていく repir(j, k - 1, 0) { res *= 2; // 注目ビットに応じて次の位置を求めつつ,値を更新していく. if (bs[j][i]) { res++; i = num_zeros[j] + bs_acc[1][j][i]; } else { i = bs_acc[0][j][i]; } } return res; } // a[l..r) に v が何個あるかを返す. int count(int l, int r, ll v) { // verify : https://judge.yosupo.jp/problem/static_range_frequency return count_sub(r, v) - count_sub(l, v); } // 昇順で c 番目の v の位置を返す. int position(ll v, int c) { if (!id.count(v)) return -1; int i = id[v] + c; rep(j, k) { if (v & (1LL << j)) { auto it = upper_bound(all(bs_acc[1][j]), i - num_zeros[j]); i = distance(bs_acc[1][j].begin(), it) - 1; } else { auto it = upper_bound(all(bs_acc[0][j]), i); i = distance(bs_acc[0][j].begin(), it) - 1; } } return i; } // a[l..r) のうち昇順で i 番目の要素を返す. ll get(int l, int r, int i) { // verify : https://judge.yosupo.jp/problem/range_kth_smallest ll res = 0; repir(j, k - 1, 0) { res *= 2; int cnt0 = bs_acc[0][j][r] - bs_acc[0][j][l]; if (i >= cnt0) { res++; l = num_zeros[j] + bs_acc[1][j][l]; r = num_zeros[j] + bs_acc[1][j][r]; i -= cnt0; } else { l = bs_acc[0][j][l]; r = bs_acc[0][j][r]; } } return res; } // a[l..r) の中で出現頻度降順に最大 c 個の要素と頻度の組を返す. void frequency(int l, int r, int c, vector& freq) { freq.clear(); priority_queue> q; q.push({ r - l, k - 1, l, r, 0 }); while (!q.empty()) { int w, j; ll v; tie(w, j, l, r, v) = q.top(); q.pop(); if (j == -1) { freq.push_back({ v, w }); if (--c == 0) return; } else { int l1 = num_zeros[j] + bs_acc[1][j][l]; int r1 = num_zeros[j] + bs_acc[1][j][r]; int l0 = bs_acc[0][j][l]; int r0 = bs_acc[0][j][r]; q.push({ r1 - l1, j - 1, l1, r1, 2 * v + 1 }); q.push({ r0 - l0, j - 1, l0, r0, 2 * v }); } } } // a[l..r) の和を返す. ll sum(int l, int r) { return acc[k][r] - acc[k][l]; } // a[l1..r1) と a[l2..r2) に共通する要素を求め, // その値とそれぞれにおける出現頻度の三つ組のリストを freq に格納する. void intersection(int l1, int r1, int l2, int r2, vector>& freq) { freq.clear(); queue> q; q.push({ k - 1, l1, r1, l2, r2, 0 }); while (!q.empty()) { int j; ll v; tie(j, l1, r1, l2, r2, v) = q.front(); q.pop(); if (l1 == r1 || l2 == r2) continue; if (j == -1) { freq.push_back({ v, r1 - l1, r2 - l2 }); } else { int l11 = num_zeros[j] + bs_acc[1][j][l1]; int r11 = num_zeros[j] + bs_acc[1][j][r1]; int l10 = bs_acc[0][j][l1]; int r10 = bs_acc[0][j][r1]; int l21 = num_zeros[j] + bs_acc[1][j][l2]; int r21 = num_zeros[j] + bs_acc[1][j][r2]; int l20 = bs_acc[0][j][l2]; int r20 = bs_acc[0][j][r2]; q.push({ j - 1, l11, r11, l21, r21, 2 * v + 1 }); q.push({ j - 1, l10, r10, l20, r20, 2 * v }); } } } // a[l..r) の中で [v0..v1) に値をもつ要素の個数を返す. int count(int l, int r, ll v0, ll v1) { // verify : https://atcoder.jp/contests/arc097/tasks/arc097_c chmax(v0, 0LL); chmin(v1, (1LL << k) - 1); if (v0 >= v1) return 0; return count_rsub(l, r, v1) - count_rsub(l, r, v0); } // a[l..r) の中で [v0..v1) に値をもつ要素の和を返す. ll sum(int l, int r, ll v0, ll v1) { chmax(v0, 0LL); chmin(v1, (1LL << k) - 1); if (v0 >= v1) return 0; return sum_rsub(l, r, v1) - sum_rsub(l, r, v0); } }; int main() { // input_from_file("input.txt"); // output_to_file("output.txt"); int n, q; cin >> n >> q; vl a(n); cin >> a; ll a_min = *min_element(all(a)); rep(i, n) a[i] -= a_min; Wavelet_matrix wm(a); rep(hoge, q) { int l, r; cin >> l >> r; l--; ll med = wm.get(l, r, (r - l) / 2); dump(med); ll res = wm.sum(l, r, med + 1, INFL); dump(res); res -= med * wm.count(l, r, med + 1, INFL); dump(res); res -= wm.sum(l, r, -INFL, med); dump(res); res += med * wm.count(l, r, -INFL, med); dump(res); cout << res << endl; } }