hdu 4288セグメントツリー+オフライン+離散化

http://acm.hdu.edu.cn/showproblem.php?pid=4288
最初は、断固たるTLEで、線分の木の上で%5=3の座標だけを維持して、例えば1 2 3 4 5 6 3番目の数を削除すると、3,6の位置を全+1にして、右にシフトしていると思いますが、和を求めるのは非常に遅いので、10秒でもTLEです..
正しいやり方:1、ノード内メンテナンスsum[0...4]はそれぞれ区間内%5=iの和を表す
2、ノードメンテナンスポイントの個数、cnt
3、離散化処理、そして挿入するたびに通過するノードcnt+1または-1、リーフノードSum[0]はノード値であり、親ノードのsumはこのように維持した:非常に良い方法

void pushup(int rt)
{
    for(int i=0;i<5;i++)
        nodes[rt].sum[i]=nodes[ls(rt)].sum[i]+nodes[rs(rt)].sum[ ((i-nodes[ls(rt)].cnt)%5+5)%5 ];
}

4、離散化+オフラインで、削除数を便利にすることができ、mapを使わない
新学会の離散化方法:

for(int i=0;i<n;i++)
{
    scanf("%d",&a[i]);
    tmp[num++]=a[i];
}
sort(tmp,tmp+num);
num=unique(tmp,tmp+num)-tmp;
//          
int pos=lower_bound(tmp,tmp+num,a[i])-tmp;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
#define IN(s) freopen(s,"r",stdin)
#define CL(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ls(rt) rt*2
#define rs(rt) rt*2+1
const int MAXN = 1e5+100;


struct Node{
    int l,r;
    ll sum[5];  //
    int cnt;    //       
}nodes[MAXN*4];

int a[MAXN],n,tmp[MAXN];
char op[MAXN][6];

void build(int rt,int l,int r)
{
    nodes[rt].l=l;
    nodes[rt].r=r;
    nodes[rt].cnt=0;
    CL(nodes[rt].sum,0);
    if(l==r)return;
    int mid=(l+r)/2;
    build(ls(rt),l,mid);
    build(rs(rt),mid+1,r);
}

void pushup(int rt)
{
    for(int i=0;i<5;i++)
        nodes[rt].sum[i]=nodes[ls(rt)].sum[i]+nodes[rs(rt)].sum[ ((i-nodes[ls(rt)].cnt)%5+5)%5 ];
}

void update(int  rt, int pos, int d, int flag)
{
    nodes[rt].cnt+=flag;
    if(nodes[rt].l == nodes[rt].r)
    {
        nodes[rt].sum[0]+=d;
        return;
    }
    if(pos<=nodes[ls(rt)].r)update(ls(rt),pos,d,flag);
    else update(rs(rt),pos,d,flag);
    pushup(rt);
}

int main()
{
    //IN("hdu4288.txt");
    int num;
    while(~scanf("%d",&n))
    {
        num=0;
        for(int i=0;i<n;i++)
        {
            scanf("%s",op[i]);
            if(op[i][0]!='s')
            {
                scanf("%d",&a[i]);
                tmp[num++]=a[i];
            }
        }
        sort(tmp,tmp+num);
        num=unique(tmp,tmp+num)-tmp;
        build(1,1,num);
        for(int i=0;i<n;i++)
        {
            int pos=lower_bound(tmp,tmp+num,a[i])-tmp;
            if(op[i][0] == 'a')update(1,pos,a[i],1);
            if(op[i][0] == 'd')update(1,pos,-a[i],-1);
            if(op[i][0] == 's')printf("%I64d
",nodes[1].sum[2]);
        }
    }
    return 0;
}