HihoCoder1333 :平衡树（splay+lazy）（区间加值，区间删除）

描述

小Ho：好麻烦啊~~~~~

小Hi：小Ho你在干嘛呢？

小Ho：我在干活啊！前几天老师让我帮忙管理一下团队的人员，但是感觉好难啊。

小Hi：说来听听？

小Ho：事情是这样的。我们有一个运动同好会，每天都有人加入或者退出，所以老师让我帮忙管理一下人员。每个成员有一个互不相同的id和他对我们同好会的兴趣值val，每隔一段时间一些成员的兴趣值就会发生变化。老师有时候也会问我一些成员的兴趣值。

小Hi：所以你就需要一个表格来管理信息咯？

小Ho：是啊，但是我们同好会的成员实在是太多了！我感觉完全搞不定啊。

小Hi：这样啊，那不如让我来帮帮你吧！

小Ho：真的吗？

小Hi：当然是真的啦，小Ho，你先告诉我有多少种需要完成的事情？

小Ho：一共有4种情况：

1. 加入：一个新的成员加入同好会，我会分配给他一个没有使用的id，并且询问他的兴趣值val。

2. 修改：id在区间[a,b]内的成员，兴趣值同时改变k，k有可能是负数，表示他们失去了对同好会的兴趣。

3. 退出：id在区间[a,b]内的成员要退出同好会，虽说是区间，也有可能只有1个人。

4. 询问：老师会问我在区间[a,b]内的成员总的兴趣值。

小Hi：我明白了，让我想一想该如何解决。

提示：Splay

输入

第1行：1个正整数n，表示操作数量，100≤n≤200,000

第2..n+1行：可能包含下面4种规则：

1个字母'I'，紧接着2个数字id,val，表示一个编号为id的新成员加入，其兴趣值为val，1≤id≤100,000,000，1≤val≤10,000,000，保证在团队中的每个人id都不相同。

1个字母'Q'，紧接着2个数字a,b。表示询问团队中id在区间[a,b]的所有成员总兴趣值，保证区间内至少有一个成员，结果有可能超过int的范围。

1个字母'M'，紧接着3个数字a,b,d，表示将团队中id在区间[a,b]的成员兴趣值都改变d，其中d有可能为负数。保证操作之后每个成员的兴趣值仍然在0~10,000,000。

1个字母'D'，紧接着2个数字a,b，表示将团队中id在区间[a,b]的成员除去。

注意有可能出现一个id为1的成员加入团队，被除去之后，又有一个新的id为1的成员加入团队的情况。

输出

若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解

ps：

如果没有新加入节点这一操作，就是线段树+laxy操作了......

有新加入节点，splay+laxy......

似乎明白了什么......

正题：

和上一个代码比较，加了id，val，tot，lazy等变量，和一些函数。

注意：查询，修改，和删除函数依旧没有加边界两点。。。

因为此处的做法是找到最大的x<a,最小的y>b（不能等于！），然后查询，修改或者删去x，y之间的（不包括x和y），这样保证处理的区间一定在[a,b]上。

 （insert如果用地址符的话，可以不单独处理root==0的情况，这里懒得改了，见下面几道题的写法。）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const int maxN=;

const ll inf=0x3f3f3f3f;

struct SplayData

{

    int fa,ch[],id,val,num;

    ll totVal,lazy;

    SplayData()//自动初始每一个新建data

    {

        totVal=val=lazy=;

        ch[]=ch[]=;

        num=fa=;

    }

};

struct SplayTree

{

    int cnt;

    int root;

    SplayData S[maxN];

    SplayTree()//自动初始树

    {

        root=;

        cnt=;

        Insert(-inf,);//插入极大极小值

        Insert(inf,);

    }

    void Find(int x)

    {

        if (root==)  return ;//树为空，肯定找不到

        int now=root;

        while ((S[now].ch[x>S[now].id]!=)&&(x!=S[now].id)) {

            now=S[now].ch[x>S[now].id];

        }

        Splay(now,);

    }

    void marking(int x,int delta)

    {

        S[x].lazy+=delta;

        S[x].totVal+=S[x].num*delta;

        S[x].val+=delta;

    }

    void update(int x)//对x

    {

        S[x].num=;

        S[x].totVal=S[x].val;

        if(S[x].ch[]){

            S[x].num+=S[S[x].ch[]].num;

            S[x].totVal+=S[S[x].ch[]].totVal;

        }

        if(S[x].ch[]){

            S[x].num+=S[S[x].ch[]].num;

            S[x].totVal+=S[S[x].ch[]].totVal;

        }

    }

    void pushdown(int x)//对x的儿子

    {

        if(S[x].ch[]) marking(S[x].ch[],S[x].lazy);

        if(S[x].ch[]) marking(S[x].ch[],S[x].lazy);

        S[x].lazy=;

        update(x);

    }

    void Insert(int id,int val)

    {

        if(root==){

            root=++cnt;

            S[root].id=id;

            S[root].val=val;

            S[root].totVal=val;

        }

        else {

            int x=bst_insert(root,id,val);

            if(x) Splay(x,);

        }

    }

    int bst_insert(int now,int id,int val)

    {

        pushdown(now);

        int tmp=;

        if(S[now].id>id){

            if(S[now].ch[]) tmp=bst_insert(S[now].ch[],id,val);

            else {

                S[++cnt].id=id;

                S[cnt].val=val;

                S[cnt].totVal=val;

                S[now].ch[]=cnt;

                S[cnt].fa=now;

                tmp=cnt;

            }

        }

        else if(S[now].id<id){

            if(S[now].ch[]) tmp=bst_insert(S[now].ch[],id,val);

            else {

                S[++cnt].id=id;

                S[cnt].val=val;

                S[cnt].totVal=val;

                S[now].ch[]=cnt;

                S[cnt].fa=now;

                tmp=cnt;

            }

        }

        update(now);

        return tmp;

    }

    void Rotate(int x)

    {

        int y=S[x].fa;

        int z=S[y].fa;

        pushdown(y);

        pushdown(x);

        int k1=S[y].ch[]==x;

        int k2=S[z].ch[]==y;

        S[z].ch[k2]=x;

        S[x].fa=z;

        S[y].ch[k1]=S[x].ch[k1^];

        S[S[x].ch[k1^]].fa=y;

        S[x].ch[k1^]=y;

        S[y].fa=x;

        update(y);

        update(x);

        return;

    }

    void Splay(const int x,int goal)

    {

        if(!x) return ;//!

        while (S[x].fa!=goal)

        {

            int y=S[x].fa;

            int z=S[y].fa;

            if (z!=goal)

                ((S[z].ch[]==y)^(S[y].ch[]==x))?Rotate(x):Rotate(y);//异则x，同则y

            Rotate(x);

        }

        if (goal==)

            root=x;

        return;

    }

    int Next(int x,int opt)

    {

        Find(x);//先移‘x’到根

        int now=root;

        if ((S[now].id<x)&&(opt==)) return now; //对根做处理,暂时没有发现这种情况。

        if ((S[now].id>x)&&(opt==)) return now;

        now=S[now].ch[opt];

        while (S[now].ch[opt^]!=)  now=S[now].ch[opt^];//沿子树一直找

        return now;

    }

    void DeleteRange(int l,int r)

    {

        Insert(l,);//防止没有边界

        Insert(r,);

        int prep=Next(l,);//移到根

        int nex=Next(r,);//移到根的右儿子

        Splay(prep,);

        Splay(nex,prep);

        S[nex].ch[]=;//删去根的右儿子的左儿子

        update(nex);

        update(prep);

    }

    ll Query(int l,int r)//这两个没有删，不能加边界。

    {

        int prep=Next(l,);//移到根

        int nex=Next(r,);//移到根的右儿子

        Splay(prep,);

        Splay(nex,prep);

        return S[S[nex].ch[]].totVal;//...

    }

    int Modify(int l,int r,int delta)

    {

        int prep=Next(l,);

        int nex=Next(r,);

        Splay(prep,);

        Splay(nex,prep);

        marking(S[nex].ch[],delta);

    }

};

SplayTree SP;

int main()

{

    int k,l,r,n,id,val,a,b;

    scanf("%d",&n);

    for (int i=;i<=n;i++){

        char opt[];

        scanf("%s",opt);

        if (opt[]=='I'){

            scanf("%d%d",&id,&val);

            SP.Insert(id,val);

        }

        else if (opt[]=='Q'){

            scanf("%d%d",&a,&b);

            printf("%lld\n",SP.Query(a,b));

        }

        else if (opt[]=='M'){

            scanf("%d%d%d",&a,&b,&val);

            SP.Modify(a,b,val);

        }

        else {

            scanf("%d%d",&a,&b);

            SP.DeleteRange(a,b);

        }

    }

    return ;

}