题意:给n个操作,插入一个元素,删除一个元素,询问已经在集合(从小到大排列有序)中%5 = 3的元素的和。
题解:线段树,维护区间长度和 % 5 = 0 1 2 3 4 的和即可。
Sure原创,转载请注明出处。
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 100002;
struct node
{
__int64 sum[5];
int len;
}seg[maxn << 2];
char op[maxn][5];
int val[maxn],x[maxn];
int n,top;
void read()
{
top = 0;
for(int i=0;i<n;i++)
{
scanf("%s",op[i]);
if(op[i][0] != 's')
{
scanf("%d",&val[i]);
x[top++] = val[i];
}
}
return;
}
void biuld(int l,int r,int num)
{
for(int i=0;i<5;i++)
{
seg[num].sum[i] = 0LL;
}
seg[num].len = 0;
if(l == r) return;
int mid = (l + r) >> 1;
biuld(l , mid , num << 1);
biuld(mid + 1 , r , num << 1 | 1);
return;
}
void UP(int num)
{
seg[num].len = seg[num << 1].len + seg[num << 1 | 1].len;
for(int i=0;i<5;i++)
{
seg[num].sum[i] = seg[num << 1].sum[i];
}
int bj = seg[num << 1].len;
for(int i=0;i<5;i++)
{
seg[num].sum[(i + bj) % 5] += seg[num << 1 | 1].sum[i];
}
return;
}
void make()
{
sort(x ,x + top);
top = unique(x , x + top) - x;
biuld(1 , top , 1);
return;
}
void update(int pos,int l,int r,int val,int cnt,int num)
{
if(l == r)
{
seg[num].len += cnt;
seg[num].sum[1] += 1LL * cnt * val;
return;
}
int mid = (l + r) >> 1;
if(pos<= mid) update(pos , l , mid , val , cnt , num << 1);
else update(pos , mid + 1 , r , val , cnt , num << 1 | 1);
UP(num);
return;
}
void solve()
{
for(int i=0;i<n;i++)
{
if(op[i][0] == 'a')
{
update(upper_bound(x , x + top , val[i]) - x , 1 , top , val[i] , 1 , 1);
}
else if(op[i][0] == 'd')
{
update(upper_bound(x , x + top , val[i]) - x , 1 , top , val[i] , -1 , 1);
}
else printf("%I64d\n",seg[1].sum[3]);
}
return;
}
int main()
{
while(~scanf("%d",&n))
{
read();
make();
solve();
}
return 0;
}