#define LOCAL #include using namespace std; #pragma region Macros typedef long long ll; typedef __int128_t i128; typedef unsigned int uint; typedef unsigned long long ull; #define ALL(x) (x).begin(), (x).end() template istream& operator>>(istream& is, vector& v) { for (T& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == (int)v.size() ? "" : " "); } return os; } template ostream& operator<<(ostream& os, const pair& p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream& operator<<(ostream& os, const map& m) { os << '{'; for (auto itr = m.begin(); itr != m.end();) { os << '(' << itr->first << ',' << itr->second << ')'; if (++itr != m.end()) os << ','; } os << '}'; return os; } template ostream& operator<<(ostream& os, const unordered_map& m) { os << '{'; for (auto itr = m.begin(); itr != m.end();) { os << '(' << itr->first << ',' << itr->second << ')'; if (++itr != m.end()) os << ','; } os << '}'; return os; } template ostream& operator<<(ostream& os, const set& s) { os << '{'; for (auto itr = s.begin(); itr != s.end();) { os << *itr; if (++itr != s.end()) os << ','; } os << '}'; return os; } template ostream& operator<<(ostream& os, const multiset& s) { os << '{'; for (auto itr = s.begin(); itr != s.end();) { os << *itr; if (++itr != s.end()) os << ','; } os << '}'; return os; } template ostream& operator<<(ostream& os, const unordered_set& s) { os << '{'; for (auto itr = s.begin(); itr != s.end();) { os << *itr; if (++itr != s.end()) os << ','; } os << '}'; return os; } template ostream& operator<<(ostream& os, const deque& v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == (int)v.size() ? "" : " "); } return os; } template void print_tuple(ostream&, const T&) {} template void print_tuple(ostream& os, const T& t) { if (i) os << ','; os << get(t); print_tuple(os, t); } template ostream& operator<<(ostream& os, const tuple& t) { os << '{'; print_tuple<0, tuple, Args...>(os, t); return os << '}'; } void debug_out() { cerr << '\n'; } template void debug_out(Head&& head, Tail&&... tail) { cerr << head; if (sizeof...(Tail) > 0) cerr << ", "; debug_out(move(tail)...); } #ifdef LOCAL #define debug(...) \ cerr << " "; \ cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n'; \ cerr << " "; \ debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template T gcd(T x, T y) { return y != 0 ? gcd(y, x % y) : x; } template T lcm(T x, T y) { return x / gcd(x, y) * y; } int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); } int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); } int botbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); } int botbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); } int popcount(signed t) { return __builtin_popcount(t); } int popcount(long long t) { return __builtin_popcountll(t); } bool ispow2(int i) { return i && (i & -i) == i; } template T ceil(T x, T y) { assert(y >= 1); return (x > 0 ? (x + y - 1) / y : x / y); } template T floor(T x, T y) { assert(y >= 1); return (x > 0 ? x / y : (x - y + 1) / y); } template inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return true; } return false; } #pragma endregion #include #include template struct LazySegmentTree { LazySegmentTree(int n, const F f, const G g, const H h, const Monoid& e, const OperatorMonoid& id) : n(n), f(f), g(g), h(h), e(e), id(id) { size = 1; height = 0; while (size < n) size <<= 1, height++; data.assign(size << 1, e); lazy.assign(size << 1, id); } void set(int k, Monoid x) { assert(0 <= k && k < n); data[k + size] = x; } void build() { for (int k = size - 1; k > 0; k--) { data[k] = f(data[k << 1 | 0], data[k << 1 | 1]); } } void update(int a, int b, const OperatorMonoid& x) { assert(0 <= a && a <= b && b <= n); if (a == b) return; thrust(a += size); thrust(b += size - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) lazy[l] = h(lazy[l], x), ++l; if (r & 1) --r, lazy[r] = h(lazy[r], x); } recalc(a); recalc(b); } void set_val(int k, Monoid x) { assert(0 <= k && k < n); thrust(k += size); data[k] = x; lazy[k] = id; recalc(k); } Monoid query(int a, int b) { assert(0 <= a && a <= b && b <= n); if (a == b) return e; thrust(a += size); thrust(b += size - 1); Monoid L = e, R = e; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) L = f(L, apply(l++)); if (r & 1) R = f(apply(--r), R); } return f(L, R); } Monoid operator[](int k) { thrust(k += size); return apply(k); } template int find_first(int l, const C& check) { assert(0 <= l && l <= n); assert(!check(e)); if (l == n) return n; Monoid L = e; if (l == 0) { if (check(f(L, apply(1)))) return find_subtree(1, check, L, false); return n; } thrust(l + size); int r = size; for (l += size, r += size; l < r; l >>= 1, r >>= 1) { if (l & 1) { Monoid nxt = f(L, apply(l)); if (check(nxt)) return find_subtree(l, check, L, false); L = nxt; l++; } } return n; } template int find_last(int r, const C& check) { assert(0 <= r && r <= n); assert(!check(e)); if (r == 0) return 0; Monoid R = e; if (r == n) { if (check(f(apply(1), R))) return find_subtree(1, check, R, true); return -1; } thrust(r + size - 1); int l = size; for (r += size; l < r; l >>= 1, r >>= 1) { if (r & 1) { Monoid nxt = f(apply(--r), R); if (check(nxt)) return find_subtree(r, check, R, true); R = nxt; } } return -1; } private: int n, size, height; std::vector data; std::vector lazy; const F f; const G g; const H h; const Monoid e; const OperatorMonoid id; inline Monoid apply(int k) { return lazy[k] == id ? data[k] : g(data[k], lazy[k]); } inline void propagate(int k) { if (lazy[k] == id) return; lazy[k << 1 | 0] = h(lazy[k << 1 | 0], lazy[k]); lazy[k << 1 | 1] = h(lazy[k << 1 | 1], lazy[k]); data[k] = apply(k); lazy[k] = id; } inline void thrust(int k) { for (int i = height; i > 0; i--) propagate(k >> i); } inline void recalc(int k) { while (k >>= 1) data[k] = f(apply(k << 1 | 0), apply(k << 1 | 1)); } template int find_subtree(int a, const C& check, Monoid& M, bool type) { while (a < size) { propagate(a); Monoid nxt = type ? f(apply(a << 1 | type), M) : f(M, apply(a << 1 | type)); if (check(nxt)) a = a << 1 | type; else M = nxt, a = (a << 1 | 1) - type; } return a - size; } }; /** * @brief Lazy Segment Tree * @docs docs/datastructure/LazySegmentTree.md */ #include #include template struct BinaryIndexedTree { BinaryIndexedTree(int n) : n(n), data(n) {} void add(int k, T x) { assert(0 <= k && k < n); for (k++; k <= n; k += k & -k) data[k - 1] += x; } T query(int l, int r) const { assert(0 <= l && l <= r && r <= n); return sum(r) - sum(l); } T operator[](int i) const { return query(i, i + 1); } int lower_bound(T x) const { if (x <= 0) return 0; int cur = 0, k = 1; while (k < n) k <<= 1; for (; k > 0; k >>= 1) { if (cur + k <= n && data[cur + k - 1] < x) { x -= data[cur + k - 1]; cur += k; } } return cur; } int upper_bound(T x) const { return lower_bound(x + 1); } private: int n; std::vector data; T sum(int r) const { T res = 0; for (; r > 0; r -= r & -r) res += data[r - 1]; return res; } }; /** * @brief Binary Indexd Tree (Fenwick Tree) * @docs docs/datastructure/BinaryIndexedTree.md */ #include #include #include #include struct Mo { Mo(int n) : n(n) {} void add(int l, int r) { assert(l <= r); left.emplace_back(l); right.emplace_back(r); } template void run(const AL& add_left, const AR& add_right, const DL& del_left, const DR del_right, const REM& rem) { int q = left.size(), width = n / std::min(std::max(sqrt(q * 2 / 3), 1), n); std::vector order(q); std::iota(order.begin(), order.end(), 0); std::sort(order.begin(), order.end(), [&](int a, int b) { int ablock = left[a] / width, bblock = left[b] / width; if (ablock != bblock) return ablock < bblock; return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]); }); int l = 0, r = 0; for (auto idx : order) { while (l > left[idx]) add_left(--l); while (r < right[idx]) add_right(r++); while (l < left[idx]) del_left(l++); while (r > right[idx]) del_right(--r); rem(idx); } } template void run(const A& add, const D& del, const REM& rem) { run(add, add, del, del, rem); } private: int n; std::vector left, right; }; /** * @brief Mo's algorithm * @docs docs/other/Mo.md * */ const int INF = 1e9; const long long IINF = 1e18; const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; const char dir[4] = {'D', 'R', 'U', 'L'}; const long long MOD = 1000000007; // const long long MOD = 998244353; const int inf = 1e9; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector a(N); for (int i = 0; i < N; i++) cin >> a[i], --a[i]; vector left(N + 1, 0), right(N + 1, 0); BinaryIndexedTree BIT1(N), BIT2(N); for (int i = 0; i < N; i++) { left[i + 1] = left[i] + BIT1.query(a[i] + 1, N); BIT1.add(a[i], 1); } for (int i = N - 1; i >= 0; --i) { right[i] = right[i + 1] + BIT2.query(0, a[i]); BIT2.add(a[i], 1); } vector l(Q), r(Q), ans(Q, 0); Mo mo(N); for (int i = 0; i < Q; i++) { cin >> l[i] >> r[i]; mo.add(--l[i], r[i]); ans[i] += left[l[i]] + right[r[i]]; } BinaryIndexedTree BIT3(N), BIT4(N); int inv = 0; auto f = [](int a, int b) { return min(a, b); }; auto g = [](int a, int b) { return a + b; }; LazySegmentTree seg(N, f, g, g, inf, 0); for (int i = 0; i < N; i++) seg.set(i, 0); seg.build(); for (int i = 0; i < N; i++) { BIT4.add(a[i], 1); seg.update(a[i] + 1, N, 1); } auto add_left = [&](int idx) { inv -= BIT4.query(0, a[idx]); BIT3.add(a[idx], -1); seg.update(0, a[idx], -1); }; auto add_right = [&](int idx) { inv -= BIT3.query(a[idx] + 1, N); BIT4.add(a[idx], -1); seg.update(a[idx] + 1, N, -1); }; auto del_left = [&](int idx) { inv += BIT4.query(0, a[idx]); BIT3.add(a[idx], 1); seg.update(0, a[idx], 1); }; auto del_right = [&](int idx) { inv += BIT3.query(a[idx] + 1, N); BIT4.add(a[idx], 1); seg.update(a[idx] + 1, N, 1); }; auto rem = [&](int idx) { ans[idx] += inv + seg.query(0, N) * (r[idx] - l[idx]); }; mo.run(add_left, add_right, del_left, del_right, rem); for (int i = 0; i < Q; i++) cout << ans[i] << '\n'; return 0; }