Codeforces 85D Sum of Medians(线段树)

时间:2021-02-20 23:52:48

题目链接:Codeforces 85D - Sum of Medians

题目大意:N个操作,add x:向集合中加入x;del x:删除集合中的x;sum:将集合排序后,将集合中全部下标i % 5 = 3的元素累加求和。

解题思路:线段树单点更新,每一个点维护5个值。分别表示从该段区间中i % 5 = t的和。然后两端区间合并时仅仅须要依据左孩子中元素的个数合并。所以有一个c表示区间上元素的个数。

由于有同样的数。所以要离线操做,将全部的数映射成位置,可是对于del则不须要映射,由于集合中肯定有才干减掉。那么add和sum操作都是能够搞定了,仅仅剩下del操作,对于del x,x肯定在集合中出现过。所以每次删除第一个x就可以,假设高速查找,要借助map和一个辅助数组,由于删除一个后要又一次映射,所以借助辅助数组。

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm> using namespace std; typedef long long ll;
const int mod = 5;
const int maxn = 1e5+5; int N, M, pos[maxn], v[maxn];
map<ll, int> G; #define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], c[maxn << 2];
ll s[maxn << 2][6]; inline void maintain (int u, int d) {
c[u] += d;
memset(s[u], 0, sizeof(s[u]));
s[u][0] = (c[u] ? pos[lc[u]] : 0);
} inline void pushup(int u) {
int t = c[lson(u)] % mod;
c[u] = c[lson(u)] + c[rson(u)];
for (int i = 0; i < mod; i++)
s[u][i] = s[lson(u)][i] + s[rson(u)][(i + mod - t) % mod];
} void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
c[u] = 0;
memset(s[u], 0, sizeof(s[u])); if (l == r)
return;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
} void modify (int u, int x, int d) {
if (lc[u] == x && rc[u] == x) {
maintain(u, d);
return;
} int mid = (lc[u] + rc[u]) / 2;
if (x <= mid)
modify(lson(u), x, d);
else
modify(rson(u), x, d);
pushup(u);
} struct OP {
int p, k, id;
OP (int k = 0, int p = 0, int id = 0) {
this->k = k;
this->p = p;
this->id = id;
}
friend bool operator < (const OP& a, const OP& b) {
if (a.k == 0)
return false;
if (b.k == 0)
return true;
if (a.p != b.p)
return a.p < b.p;
return a.id < b.id;
}
}; inline bool cmp (const OP& a, const OP& b) {
return a.id < b.id;
} vector<OP> vec; void init () {
scanf("%d", &N);
char op[5];
int x; for (int i = 1; i <= N; i++) {
scanf("%s", op);
if (op[0] == 's')
vec.push_back(OP(0, 0, i));
else {
scanf("%d", &x);
vec.push_back(OP(op[0] == 'a' ? 1 : -1, x, i));
}
} M = 1;
sort(vec.begin(), vec.end());
for (int i = 0; i < N; i++) {
if (vec[i].k < 0)
continue;
if (vec[i].k == 0)
break; pos[M] = vec[i].p;
vec[i].p = M++;
}
build(1, 1, M);
} void solve () {
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < N; i++) {
//printf("%d %d!\n", vec[i].k, pos[vec[i].p]);
if (vec[i].k == 0)
printf("%lld\n", s[1][2]);
else if (vec[i].k == -1) {
int tmp = vec[i].p;
v[G[tmp]] = 0;
modify(1, G[tmp], -1); if (G[tmp] <= N && v[G[tmp]+1] && pos[G[tmp]] == pos[G[tmp]+1])
G[tmp]++;
else
G[tmp] = 0;
} else {
int tmp = pos[vec[i].p];
v[vec[i].p] = 1;
modify(1, vec[i].p, 1);
if (G[tmp] == 0)
G[tmp] = vec[i].p;
}
}
} int main () {
init();
solve();
return 0;
}