HDU 4288 Coder（12年成都网络赛-线段树）

题目链接：Click here~~

题意：

维护一个有序数列{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)。

#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;}