题意略。
离线处理,离散化。然后就是简单的线段树了。需要根据mod 5的值来维护。具体看代码了。
/*
线段树+离散化+离线处理
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
#define N 100010
ll sum[N<<2][5];
int a[N], n, m, cnt[N<<2];
struct node {
char c;
int x;
} q[N];
void Up(int rt) {
cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];
for (int i=0; i<5; i++)
sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][(i-cnt[rt<<1]%5+5)%5];
}
void add(int idx, int val, int l, int r, int rt) {
if (l == r) {
cnt[rt] = 1;
sum[rt][1] = val;
return ;
}
int mid = (l + r) >> 1;
if (idx <= mid) add(idx, val, l, mid, rt<<1);
else add(idx, val, mid+1, r, rt<<1|1);
Up(rt);
}
void del(int idx, int l, int r, int rt) {
if (l == r) {
sum[rt][1] = cnt[rt] = 0;
return ;
}
int mid = (l + r) >> 1;
if (idx <= mid) del(idx, l, mid, rt<<1);
else del(idx, mid+1, r, rt<<1|1);
Up(rt);
}
int main() {
char s[10];
while (scanf("%d", &n) == 1) {
m = 0;
for (int i=0; i<n; i++) {
scanf(" %s", s);
q[i].c = s[0];
if (s[0] != 's') {
scanf("%d", &q[i].x);
a[m++] = q[i].x;
}
}
sort(a, a+m);
m = unique(a, a+m) - a;
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
int pos;
for (int i=0; i<n; i++) {
if (q[i].c == 's') printf("%I64d\n", sum[1][3]);
else {
pos = lower_bound(a, a+m, q[i].x) - a + 1;
if (q[i].c == 'a') add(pos, q[i].x, 1, m, 1);
else del(pos, 1, m, 1);
}
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 1166线段树
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
离线OJ题库(HDU ZJU等,部分有答案),需联网。
hdu 1695 GCD(欧拉函数+容斥原理).docx
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 ...
Problem Description 话说,经过了漫长的一个...本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面输出输出A+B的值,请输出最简形式。