#include <bits/stdc++.h> #define BT ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); #define ll long long #define MAXN 100010 using namespace std; int n, q, a, b, arr[MAXN], sum1[MAXN], sum2[MAXN]; int main() { BT cin >> n >> q; int i, j, k; for (i = 0; i < n; i++) cin >> arr[i]; for (i = 0, j = 1, k = 1; i < n; i++, j++, k++) { while (j < arr[i]) { sum1[j] = sum1[j - 1]; j++; } sum1[j] = arr[i] + sum1[j - 1]; while (k < arr[i]) { sum2[k] = sum2[k - 1]; k++; } sum2[k] = sum2[k - 1] + 1; } while (q--) { cin >> a >> b; if (a > b) a += b, b = a - b, a -= b; int t = (a + b) / 2; ll sum = (a * sum2[a] - sum1[a]) + ((sum1[t] - sum1[a]) - a * (sum2[t] - sum2[a])) + (b * (sum2[b] - sum2[t]) - (sum1[b] - sum1[t])) + ((sum1[j - 1] - sum1[b]) - b * (sum2[k - 1] - sum2[b])); cout << sum << endl; } return 0; }
全部评论
(0) 回帖