Hihocoder #1333 : 平衡树·Splay2

1333 : 平衡树·Splay2

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小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：我明白了，让我想一想该如何解决。

输入

第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个整数，表示针对询问的回答，保证一定有合法的解

样例输入

9

I 1 1

I 2 2

I 3 3

Q 1 3

M 1 2 2

Q 1 3

D 2 3

I 4 2

Q 1 4

样例输出

6

10

5

/*

splay 值域区间修改+区间删除+区间查询+tagpush.

*/

#include<iostream>

#include<cstdio>

#define MAXN 200011

#define LL long long

#define INF 1e9

using namespace std;

int n,m,tot,size[MAXN],s[MAXN],id[MAXN],fa[MAXN],tree[MAXN][2],root,tag[MAXN],t1,t2;

LL sum[MAXN];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void push(int k)

{

    if(tree[k][0]) s[tree[k][0]]+=tag[k];

    if(tree[k][1]) s[tree[k][1]]+=tag[k];

    if(tree[k][0]) tag[tree[k][0]]+=tag[k];

    if(tree[k][1]) tag[tree[k][1]]+=tag[k];

    if(tree[k][0]) sum[tree[k][0]]+=tag[k]*size[tree[k][0]];

    if(tree[k][1]) sum[tree[k][1]]+=tag[k]*size[tree[k][1]];

    tag[k]=0;return ;

}

void rotate(int x,int &k)

{

    int y=fa[x],z=fa[y],l,r;

    if(tree[y][0]==x) l=0;else l=1;r=l^1;

    if(tag[z]) push(z);

    if(tag[y]) push(y);

    if(tag[x]) push(x);

    if(y==k) k=x;

    else{

        if(tree[z][0]==y) tree[z][0]=x;

        else tree[z][1]=x;

    }

    fa[x]=z;fa[y]=x;fa[tree[x][r]]=y;

    tree[y][l]=tree[x][r],tree[x][r]=y;

    size[y]=size[tree[y][0]]+size[tree[y][1]]+1;

    size[x]=size[tree[x][0]]+size[tree[x][1]]+1;

    sum[y]=sum[tree[y][0]]+sum[tree[y][1]]+s[y];

    sum[x]=sum[tree[x][0]]+sum[tree[x][1]]+s[x];

    return ;

}

void splay(int x,int &k)

{

    int y,z;

    while(x!=k)

    {

        y=fa[x],z=fa[y];

        if(y!=k)

        {

            if((tree[z][0]==y)^(tree[y][0]==x)) rotate(x,k);

            else rotate(y,k);

        }

        rotate(x,k);

    }

    return ;

}

void add(int &k,int f,int x,int y)

{

    if(!k){k=++tot;s[tot]=y;id[tot]=x;size[tot]=1;sum[k]=y;fa[tot]=f;splay(k,root);return ;}

    if(tag[k]) push(k);

    if(x<=id[k]) add(tree[k][0],k,x,y);

    else add(tree[k][1],k,x,y);

    return ;

}

void before(int k,int x)

{

    if(!k) return ;

    if(tag[k]) push(k);

    if(x>=id[k]){t1=k;before(tree[k][1],x);return ;}

    else before(tree[k][0],x);

    return ;

}

void after(int k,int x)

{

    if(!k) return ;

    if(tag[k]) push(k);

    if(x<=id[k]){t2=k;after(tree[k][0],x);return ;}

    else after(tree[k][1],x);

    return ;

}

void slovequery(int x,int y)

{

    before(root,x-1);

    after(root,y+1);

    splay(t1,root),splay(t2,tree[t1][1]);

    printf("%lld\n",sum[tree[t2][0]]);

    return ;

}

void slovedelete(int x,int y)

{

    before(root,x-1);

    after(root,y+1);

    splay(t1,root),splay(t2,tree[t1][1]);

    tree[t2][0]=0;splay(t2,root);

    return ;

}

void slovechange(int x,int y,int z)

{

    before(root,x-1);

    after(root,y+1);

    splay(t1,root),splay(t2,tree[t1][1]);

    tag[tree[t2][0]]+=z,sum[tree[t2][0]]+=z*size[tree[t2][0]];

    s[tree[t2][0]]+=z;

    splay(tree[t2][0],root);

    return ;

}

int main()

{

    int x,y,z;

    n=read();char ch[2];

    add(root,root,-INF,0),add(root,root,INF,0);

    while(n--)

    {

        scanf("%s",ch);

        if(ch[0]=='I') x=read(),y=read(),add(root,root,x,y);

        else if(ch[0]=='Q') x=read(),y=read(),slovequery(x,y);

        else if(ch[0]=='M') x=read(),y=read(),z=read(),slovechange(x,y,z);

        else x=read(),y=read(),slovedelete(x,y);

    }

    return 0;

}

巴特西

Hihocoder #1333 : 平衡树·Splay2

1333 : 平衡树·Splay2

最新文章

热门文章