Codeforces 85D Sum of Medians(线段树)[通俗易懂]

Codeforces 85D Sum of Medians(线段树)

大家好,又见面了,我是全栈君。

题目链接: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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116117.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • nacicat15激活码_通用破解码

    nacicat15激活码_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 粒子群优化算法(PSO)简介及MATLAB实现[通俗易懂]

    粒子群优化算法(PSO)简介及MATLAB实现[通俗易懂]目录粒子群优化算法概述PSO算法步骤PSO(粒子群优化算法)与GA(遗传算法)对比PSO的MATLAB实现粒子群优化算法概述•粒子群优化(PSO,particleswarmoptimization)算法是计算智能领域,除了蚁群算法,鱼群算法之外的一种群体智能的优化算法,该算法最早由Kennedy和Eberhart在1995年提出的,该算法源自对鸟类捕食问题的研究。…

  • 微商代理分销系统

    微商代理分销系统微云基石微商代理分销系统TM(简称:微商代理分销系统TM),是所有微商分销系统中第一个采用二级无限分销模式的系统,两级分销比例由商家设定,系统自动记录追踪用户IP并管理成为分销商的前后层级。移动互联网的泛传播性很强,记录追踪用户的分销可以帮助商家梳理信息、制定市场营销策略及着重发展哪些分销商。《2014年中国商铺用户微信运营调研报告》中显示,45.7%的中小商家表示看好微商运营,39.1%

  • python微信刷屏_拍一拍,微信史上最短一行代码

    python微信刷屏_拍一拍,微信史上最短一行代码今日推文说明二条:Python办公自动化|从Word到Excel三条:17个Python的牛逼骚操作,你都OK吗?↑关注+星标,后台回复【大礼包】送你Python自学大礼包图片来自不正经程序员…

  • git下载安装教程

    git下载安装教程git下载安装教程前言:因为最近突然对使用github搭建一个自己的网站并绑定域名特别着迷,但是前提条件是必须得安装git,于是便把安装过程记录下来,便利自己,帮助他人。1.访问git官网下载最新版本git官方网页:https://git-scm.com/download/win在git官网中,有不同操作系统下的git,选择符合自己电脑版本的进行下载就可以了这里我选择的windows,然后根据自己电脑是32位还是64位,在下面两个选项中选择选择好了静待其下好就好了或许会有下载缓慢或无法下

  • Java开发手册之控制语句

    Java开发手册之控制语句Java开发手册之控制语句

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号