Hdu4288_Coder(线段树)

80 阅读 0 评论 53 点赞

我是靠谱客的博主秀丽萝莉，最近开发中收集的这篇文章主要介绍Hdu4288_Coder(线段树)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

题目中给了三个操作
1：add x 就是把x插进去
2：delete x 就是把x删除
3：sum 就是求下标%5=3的元素的和。
插入和删除最后都要保证数列有序。

思路：

线段树做法：每个节点维护两个值，一个是当前区间的数字个数cnt，另一个是sum[i]，sum[i]就是区间内数的下标%5 = i的这些数的和（下标是指当前区间内的，不是整体区间）。
向上更新时，父亲的左区间的下标与左儿子的下标mod5的情况完全相同，右区间的第x元素下标在父区间中应该对应的是第(x+左区间的元素个数)个元素。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson root<<1, l, mid
#define rson root<<1|1, mid+1, r
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int maxn = 1e5+5;
char op[maxn][10];
int n, dat[maxn], tmp[maxn];
struct Node{
int cnt;
LL sum[5];
}Tree[maxn<<2];
void Stree_build(int root, int l, int r){
for(int i = 0; i < 5; ++i) Tree[root].sum[i] = 0; Tree[root].cnt = 0;
if(l == r) return;
int mid = (l+r) >> 1;
Stree_build(lson);
Stree_build(rson);
}
void push_up(int root){
Tree[root].cnt = Tree[root<<1].cnt + Tree[root<<1|1].cnt;
for(int i = 0; i < 5; ++i)
Tree[root].sum[i] = Tree[root<<1].sum[i] + Tree[root<<1|1].sum[(i-Tree[root<<1].cnt%5+5)%5];
}
// flag表示+ or -
void update(int k, int l, int r, int root, int val, int flag){
if(l == r){
Tree[root].cnt+= flag;
Tree[root].sum[1] = (LL)val;
return;
}
int mid = (l+r) >> 1;
if(k <= mid)
update(k, l, mid, root<<1, val, flag);
else
update(k, mid+1, r, root<<1|1, val, flag);
push_up(root);
}
int main()
{
freopen("in.txt","r",stdin);
int x;
while(scanf("%d",&n) == 1&&n){
int len = 0;
for(int i = 0; i < n; ++i){
scanf("%s", op[i]);
if(op[i][0] != 's'){
scanf("%d", &x);
dat[i] = x;
tmp[len++] = x;
}
}
sort(tmp, tmp+len);
len = unique(tmp, tmp+len) - tmp;
Stree_build(1, 1, len);
int pos;
for(int i = 0; i < n; ++i){
pos = lower_bound(tmp, tmp+len, dat[i]) - tmp+1;
if(op[i][0] == 'a'){
//printf("pos = %d, len = %d, v = %dn",pos,len,dat[i]);
update(pos, 1, len, 1, dat[i], 1);
}
else if(op[i][0] == 'd') update(pos, 1, len, 1, 0, -1);
else printf("%lldn", Tree[1].sum[3]);
}
}
return 0;
}

也可以暴力：

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int maxn = 1e5+5;
int n, x, A[maxn];
char op[10];
int main()
{
freopen("in.txt","r",stdin);
while(scanf("%d",&n) == 1&&n){
int len = 0;
for(int k = 0; k < n; ++k){
scanf("%s", op);
if(op[0] == 'a'){
scanf("%d", &x);
int i;
for(i = len++; i > 0; --i){
if(x >= A[i]) break;
A[i+1] = A[i];
}
A[i+1] = x;
}
else if(op[0] == 'd'){
scanf("%d", &x);
int i;
//
for(i = 1; i <= len; ++i)
//
if(x == A[i]) break;
//
for(; i <= len; ++i)
//
A[i] = A[i+1];
int tmp = A[len], t2;
for(i = len; i > 0; --i){
if(x == tmp) break;
int t2 = tmp;
tmp = A[i-1];
A[i-1] = t2;
}
--len;
}
else{
LL ans = 0;
for(int i = 3; i <= len; i+= 5)
ans+= (LL)A[i];
printf("%lldn", ans);
}
}
}
fclose(stdin);
return 0;
}