題意：
維護一個有序數列{An}，有三種操作：
1、添加一個元素。
2、刪除一個元素。
3、求數列中下標%5 = 3的值的和。
解題思路：
看的各種題解，今天終於弄懂了。
由於線段樹中不支持添加、刪除操作，所以題解寫的是用離線做法。
我們來看它是如何解決添加、刪除的問題的。
首先將所有出現過的數記錄下來，然後排序去重，最後根據去重結果建樹，然後每個操作數都會對應線段樹中的一個點。
遇到添加、刪除操作的時候，只要把那個節點的值改變，然後將它對下標的影響處理好就可以。
那麼如何處理這些操作對下標的影響呢？
現在我們考慮一個父區間，假設它的左右子區間已經更新完畢。
顯然，左區間中下標%5的情況與父區間中%5的情況完全相同；
可是，右區間中卻不一定相同，因為右區間中的下標是以 mid 當作 1 開始的。
那麼，只要我們知道左區間中有效元素的個數 cnt，我們就能知道右區間中的下標 i 在父區間中對應的下標為 i+cnt。
所以，雖然我們最終要的只是總區間中下標%5 = 3的和。但是在更新時我們需要知道右區間%5的所有情況。
於是我們要在線段樹的每個節點開一個 sum[5] 和一個 cnt，分別記錄這個節點中下標%5的5種情況的和與有效元素的個數。
而查詢時，直接訪問總區間的 sum[3] 即可。
如此，題目便可解了。復雜度O(M logN logN)。
[cpp]
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100003
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
typedef __int64 LL;
int num[N],x[N]; //num記錄對應操作的數，x記錄對應的區間存的數
int add;
struct Tnode
{
int l,r,cnt;
LL sum[5];
}T[N<<2];
void Build(int u,int l,int r)
{
T[u].l = l , T[u].r = r;
if(l == r-1)
{
memset(T[u].sum,0,sizeof(T[u].sum));
T[u].cnt = 0;
return ;
}
int mid = MID(l,r);
Build(L(u),l,mid);
Build(R(u),mid,r);
memset(T[u].sum,0,sizeof(T[u].sum));
T[u].cnt = 0;
}
void Updata(int u,int l,int r)
{
add ? ++T[u].cnt : --T[u].cnt;
if(T[u].l == T[u].r - 1)
{
T[u].sum[1] = add * x[l-1];
return ;
}
int mid = MID(T[u].l,T[u].r);
if(l >= mid)
Updata(R(u),l,r);
else
Updata(L(u),l,r);
for(int i=0;i<5;i++)
{
int j = (i + T[L(u)].cnt) % 5;
T[u].sum[j] = T[L(u)].sum[j] + T[R(u)].sum[i];
}
}
int main()
{
int Q;
char cmd[N],ccmd[4];
while(~scanf("%d",&Q))
{
int top = 0;
for(int i=0;i<Q;i++)
{
scanf("%s",ccmd);
cmd[i] = ccmd[0];
if(cmd[i] != 's')
scanf("%d",&num[top++]);
}
memcpy(x,num,sizeof(int)*top);
sort(x,x+top);
int n = unique(x,x+top) - x;
Build(1,1,n+1);
for(int i=0,j=0;i<Q;i++)
{
if(cmd[i] == 's')
{
printf("%I64d\n",T[1].sum[3]);
continue;
}
int k = lower_bound(x,x+n,num[j++]) - x + 1;
add = cmd[i] == 'a' ? 1 : 0;
Updata(1,k,k+1);
}
}
return 0;
}
