[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
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
return 0;
}
