Untitled
unknown
plain_text
5 months ago
2.3 kB
11
Indexable
#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 9; #define int long long struct node { int cnt[41] = {0}; int inv; }; int a[N], n, q; node marge(node l, node r) { node res; res.inv = l.inv + r.inv; for (int i = 1; i <= 40; i++) { if (l.cnt[i] == 0) continue; for (int j = 1; j < i; j++) { res.inv += l.cnt[i] * r.cnt[j]; } } for (int i = 1; i <= 40; i++) { res.cnt[i] = l.cnt[i] + r.cnt[i]; } return res; } struct ST { node t[4 * N]; static const int inf = 1e9; void build(int n, int b, int e) { if (b == e) { t[n].cnt[a[b]] = 1; t[n].inv = 0; return; } int mid = (b + e) >> 1, l = n << 1, r = l | 1; build(l, b, mid); build(r, mid + 1, e); t[n] = marge(t[l], t[r]); } void upd(int n, int b, int e, int i, int x) { if (b > i || e < i) return; if (b == e && b == i) { t[n].cnt[a[i]]--; t[n].cnt[x]++; return; } int mid = (b + e) >> 1, l = n << 1, r = l | 1; upd(l, b, mid, i, x); upd(r, mid + 1, e, i, x); t[n] = marge(t[l], t[r]); } node query(int n, int b, int e, int i, int j) { if (b > j || e < i) { node res; res.inv = 0; return res; } if (b >= i && e <= j) return t[n]; int mid = (b + e) >> 1, l = n << 1, r = l | 1; auto L = query(l, b, mid, i, j); auto R = query(r, mid + 1, e, i, j); return marge(L, R); } } t; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; t.build(1, 1, n); while (q--) { int ty; cin >> ty; if (ty == 1) { int l, r; cin >> l >> r; auto tt = t.query(1, 1, n, l, r); cout << t.query(1, 1, n, l, r).inv << '\n'; } else { int i, x; cin >> i >> x; t.upd(1, 1, n, i, x); a[i] = x; } } return 0; }
Editor is loading...
Leave a Comment