HDU-4288

83 阅读 0 评论 55 点赞

我是靠谱客的博主儒雅寒风，最近开发中收集的这篇文章主要介绍HDU-4288，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

一开始有一个空的数列，下标从1开始，然后给定三种操作：

1、向数列里添加一个数字。

2、删除数列中的一个数字。

3、查询由小到大排序后的数列中所有下标值对5取模为3的数之和。

解法：

我们可以用线段树来解决这个问题，首先将所有的操作保存下来，再将操作中所有出现的数字排序然后去重，离散化后建树即可。（也就是离线操作）

线段树中每个节点保存当前区间内有多少数字，以及下标值对5取模后5种结果的数字之和，还有当前区间应该调用哪一种结果的值。

例：long long ans[5] //定义

ans[0]就为当前区间内所有下标值模5为0的数字之和，ans[1]、ans[2]、ans[3]、ans[4]以此类推。

建好树后再遍历一次操作，遇到add和del操作就更新树的状态，遇到sum就输出一次结果。

更新线段树的时候要注意，右子树区间内数字的个数会影响到左子树中应当选取ans[]中的哪一个结果，在递归回上一级时要注意更新。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
struct node{
int num,x;
long long v[5];
};
int size;
int value[100005],temp[100005];
char str[100005][5];
node tree[400005];
void MakeTree(int now,int left,int right){
if(left == right){
memset(tree[now].v,0,sizeof(tree[now].v));
tree[now].num = 0;
tree[now].x = 2;
return;
}
int middle = (left+right)/2;
MakeTree(now*2,left,middle);
MakeTree(now*2+1,middle+1,right);
memset(tree[now].v,0,sizeof(tree[now].v));
tree[now].num = 0;
tree[now].x = 2;
}
int Find(int a){
int left=0,right=size-1,middle=(left+right)/2;
while(a != value[middle]){
if(a < value[middle]) right = middle-1;
else left = middle+1;
middle = (left+right)/2;
}
return middle;
}
void Add(int now,int left,int right,int p,int V){
if(left == right){
tree[now].num++;
tree[now].v[0] = V;
return;
}
int middle = (left+right)/2;
if(p<=middle) Add(now*2,left,middle,p,V);
else Add(now*2+1,middle+1,right,p,V);
tree[now].num++;
int temp = tree[now*2].num%5;
tree[now*2+1].x = (5-temp)%5;
for(int i=0;i<5;i++){
tree[now].v[i] = tree[now*2].v[i]+tree[now*2+1].v[(tree[now*2+1].x+i)%5];
}
}
void Del(int now,int left,int right,int p){
if(left == right){
tree[now].num--;
tree[now].v[0] = 0;
return;
}
int middle = (left+right)/2;
if(p<=middle) Del(now*2,left,middle,p);
else Del(now*2+1,middle+1,right,p);
tree[now].num--;
int temp = tree[now*2].num%5;
tree[now*2+1].x = (5-temp)%5;
for(int i=0;i<5;i++){
tree[now].v[i] = tree[now*2].v[i]+tree[now*2+1].v[(tree[now*2+1].x+i)%5];
}
}
int main(){
int n,i;
while(cin>>n){
memset(value,0,sizeof(value));
for(i=0;i<n;i++){
scanf("%s",&str[i]);
if(str[i][0] == 's') continue;
scanf("%d",&value[i]);
}
memcpy(temp,value,sizeof(temp));
sort(value,value+n);
for(i=n-1;i>0;i--){
if(value[i] == value[i-1]) value[i] = 1000000007;
}
if(value[0] == 0) value[i] = 1000000007;
sort(value,value+n);
for(i=n-1;i>=0;i--){
if(value[i] != 1000000007) break;
}
size = i+1;
memset(tree,0,sizeof(tree));
MakeTree(1,0,size-1);
for(i=0;i<n;i++){
if(str[i][0] == 's') printf("%I64dn",tree[1].v[tree[1].x]);
else if(str[i][0] == 'a') Add(1,0,size-1,Find(temp[i]),temp[i]);
else Del(1,0,size-1,Find(temp[i]));
}
}
return 0;
}