[51Nod 1394 差和问题]树状数组

xiaoxiao2021-02-28  8

[51Nod 1394 差和问题]树状数组

分类:Data Structure FenwickedTree

1. 题目链接

[51Nod 1394 差和问题]

2. 题意描述

3. 解题思路

首先离线所有操作,并且所有数字进行离散化。 然后用树状数组维护每个数字出现的次数以及区间和。 对于操作1和操作2,我们可以看成一个单点更新的操作。 但是对于操作3的询问操作,似乎不能直接查询。不过既然答案是全局的,那就可以在操作1和操作2更新之后,记录每次修改对答案的贡献。

4. 实现代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll infl = 0x3f3f3f3f3f3f3f3fLL; template<typename T> inline void umax(T &a, T b) { a = max(a, b); } template<typename T> inline void umin(T &a, T b) { a = min(a, b); } void debug() { cout << endl; } template<typename T, typename ...R> void debug (T f, R ...r) { cout << "[" << f << "]"; debug (r...); } const int MAXN = 100005; int n, q, m; ll a[MAXN]; pll tr[MAXN << 1]; void update(int p, int flag, ll v) { while (p <= m) { tr[p].first += flag; tr[p].second += flag * v; p += p & (-p); } } pll query(int p) { pll ret(0, 0); while (p > 0) { ret.first += tr[p].first; ret.second += tr[p].second; p -= p & (-p); } return ret; } pll query(int l, int r) { if (l > r) return make_pair(0, 0); pll lop = query(l - 1), rop = query(r); return make_pair(rop.first - lop.first, rop.second - lop.second); } int main() { #ifdef ___LOCAL_WONZY___ freopen("input.txt", "r", stdin); #endif // ___LOCAL_WONZY___ cin >> n >> q; vector<ll> f; for (int i = 1; i <= n; ++i) { cin >> a[i]; f.push_back(a[i]); } vector<pll> qr(q + 1); ll op, v; for (int i = 1; i <= q; ++i) { cin >> op; if (op == 3) { qr[i] = pii(3, 0); } else { cin >> v; qr[i] = pii(op, v); f.push_back(v); } } sort(f.begin(), f.end()); f.erase(unique(f.begin(), f.end()), f.end()); m = f.size(); ll ans = 0; for (int i = 1; i <= n; ++i) { int id = lower_bound(f.begin(), f.end(), a[i]) - f.begin() + 1; update(id, 1, a[i]); pll lop = query(1, id - 1), rop = query(id + 1, m); ans += (lop.first * a[i] - lop.second) + (rop.second - rop.first * a[i]); } for (int i = 1; i <= q; ++i) { tie(op, v) = qr[i]; if (op == 3) { printf("%lld\n", ans); } else { int type = op == 1 ? 1 : -1; int id = lower_bound(f.begin(), f.end(), v) - f.begin() + 1; if (type == -1 && query(id, id) == pll(0, 0)) { printf("-1\n"); continue; } update(id, type, v); pll lop = query(1, id - 1), rop = query(id + 1, m); ans += type * ((lop.first * v - lop.second) + (rop.second - rop.first * v)); } } #ifdef ___LOCAL_WONZY___ cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << "ms." << endl; #endif // ___LOCAL_WONZY___ return 0; }
转载请注明原文地址: https://www.6miu.com/read-1400212.html

最新回复(0)