【CF85D】Sum of Medians
In one well-known
algorithm of finding the k-th order statistics we should divide all
elements into groups of five consecutive elements and find the median of each
five. A median is called the middle element of a sorted array (it's the third
largest element for a group of five). To increase the algorithm's performance
speed on a modern video card, you should be able to find a sum of medians in
each five of the array.
A sum of
medians of a sorted k-element set S = {a1, a2, ..., ak},
where a1 < a2 < a3 < ... < ak,
will be understood by as
The 
operator stands for taking the
remainder, that is 
stands for the remainder of
dividing x by y.
operator stands for taking the
remainder, that is stands for the remainder of
dividing x by y.
To organize
exercise testing quickly calculating the sum of medians for a
changing set was needed.
Input
The first line
contains number n (1 ≤ n ≤ 105), the number
of operations performed.
Then each of n lines
contains the description of one of the three operations:
·
add x — add the element x to
the set;
·
del x — delete the element x from
the set;
·
sum — find the sum of medians of the set.
For any add x operation
it is true that the element x is not included in the set
directly before the operation.
For any del x operation
it is true that the element x is included in the set directly
before the operation.
All the numbers in
the input are positive integers, not exceeding 109.
Output
For each
operation sum print on the single line the sum of medians of
the current set. If the set is empty, print 0.
Please, do not use
the %lld specificator to read or write 64-bit integers in C++. It is
preferred to use the cin, cout streams (also you may use
the %I64d specificator).
Examples
Input
6
add 4
add 5
add 1
add 2
add 3
sum
add 4
add 5
add 1
add 2
add 3
sum
Output
3
Input
14
add 1
add 7
add 2
add 5
sum
add 6
add 8
add 9
add 3
add 4
add 10
sum
del 1
sum
add 1
add 7
add 2
add 5
sum
add 6
add 8
add 9
add 3
add 4
add 10
sum
del 1
sum
Output
5
11
13
11
13
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include "bits/stdc++.h"
#define mem(x) memset((x), 0, sizeof((x)))
#define il __attribute__((always_inline))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#if __cplusplus > 201403L
#define r
#else
#define r register
#endif
#define c const
namespace _c
{
c double pi = acos(-1.0);
namespace min
{
c int i8 = -128;
c int i16 = -32768;
c int i = -2147483647 - 1;
c ll l = -9223372036854775807LL - 1;
} // namespace min
namespace max
{
c int i8 = 127;
c int i16 = 32767;
c int i = 2147483647;
c ll l = 9223372036854775807LL;
} // namespace max
} // namespace _c
namespace _f
{
template <typename T>
inline c T gcd(T m, T n)
{
while (n != 0)
{
T t = m % n;
m = n;
n = t;
}
return m;
}
template <typename T>
inline c T abs(c T &a)
{
return a > 0 ? a : -a;
}
template <typename T>
inline T pow(T a, T b)
{
T res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
template <typename T>
inline T pow(T a, T b, c T &m)
{
a %= m;
T res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
return res % m;
}
} // namespace _f
namespace io
{
template <typename T>
inline T read()
{
r T res = 0, neg = 1;
char g = getchar();
for (; !isdigit(g); g = getchar())
{
if (g == '-')
{
neg = -1;
}
}
for (; isdigit(g); g = getchar())
{
res = res * 10 + g - '0';
}
return res * neg;
}
template <typename T>
inline void read(T &t)
{
t = read<T>();
}
template <typename T>
inline void readln(c T first, c T last)
{
for (r T it = first; it != last; it++)
{
read(*it);
}
}
template <typename T>
inline void _write(T x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
_write(x / 10);
}
putchar(x % 10 + '0');
}
template <typename T>
inline void write(c T &x, c char &sep = ' ')
{
_write(x);
putchar(sep);
}
template <typename T>
inline void writeln(c T &x)
{
write(x, '\n');
}
template <typename T>
inline void writeln(c T first, c T last, c char &sep = ' ', c char &ends = '\n')
{
for (r T it = first; it != last; it++)
{
write(*it, sep);
}
putchar(ends);
}
#if __cplusplus >= 201103L
template <typename T, typename... Args>
void read(T &x, Args &... args)
{
read(x);
read(args...);
}
#endif
} // namespace io
#undef c
#undef r
const int N = 1e5 + 5;
int b[N];
template <typename Tp>
struct WeightSegmentTree
{
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define ls lson(rt)
#define rs rson(rt)
struct node
{
Tp mod[5], siz;
} tree[N * 4];
inline void push_up(const Tp &rt)
{
tree[rt].siz = tree[ls].siz + tree[rs].siz;
for (register int i = 0; i <= 4; i++)
{
tree[rt].mod[i] = tree[ls].mod[i];
}
for (register int i = 0; i <= 4; i++)
{
tree[rt].mod[(i + tree[ls].siz) % 5] += tree[rs].mod[i];
}
}
inline void insert(const Tp &rt, const Tp &l, const Tp &r, const Tp &pos)
{
if (l == r)
{
tree[rt].mod[1] = b[pos];
tree[rt].siz = 1;
}
else
{
Tp mid = (l + r) >> 1;
if (pos <= mid)
{
insert(ls, l, mid, pos);
}
else
{
insert(rs, mid + 1, r, pos);
}
push_up(rt);
}
}
inline void erase(const Tp &rt, const Tp &l, const Tp &r, const Tp &pos)
{
if (l == r)
{
tree[rt].mod[1] = tree[rt].siz = 0;
}
else
{
Tp mid = (l + r) >> 1;
if (pos <= mid)
{
erase(ls, l, mid, pos);
}
else
{
erase(rs, mid + 1, r, pos);
}
push_up(rt);
}
}
#undef ls
#undef rs
#undef lson
#undef rson
};
WeightSegmentTree<ll> Seg;
int n, _n;
char s[10];
struct _q
{
int op, x;
} q[N];
int main()
{
io::read(n);
for (register int i = 1, x; i <= n; i++)
{
scanf("%s", s);
switch (s[0])
{
case 'a':
{
x = io::read<int>();
q[i] = (_q){1, x};
b[++_n] = x;
break;
}
case 'd':
{
x = io::read<int>();
q[i] = (_q){2, x};
b[++_n] = x;
break;
}
case 's':
{
q[i] = (_q){3, 0};
break;
}
default:
{
break;
}
}
}
sort(b + 1, b + _n + 1);
_n = unique(b + 1, b + _n + 1) - 1 - b;
for (register int i = 1; i <= n; i++)
{
if (q[i].x)
{
q[i].x = lower_bound(b + 1, b + _n + 1, q[i].x) - b;
}
}
for (register int i = 1; i <= n; i++)
{
switch (q[i].op)
{
case 1:
{
Seg.insert(1, 1, _n, q[i].x);
break;
}
case 2:
{
Seg.erase(1, 1, _n, q[i].x);
break;
}
case 3:
{
io::writeln(Seg.tree[1].mod[3]);
break;
}
default:
{
break;
}
}
}
}
评论
发表评论