首页 > 代码库 > hihocoder #1333 : 平衡树·Splay2

hihocoder #1333 : 平衡树·Splay2

2024-08-12 15:05:48   225人阅读

描述

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

样例输入
9I 1 1I 2 2I 3 3Q 1 3M 1 2 2Q 1 3D 2 3I 4 2Q 1 4
样例输出
6105
EmacsNormalVim

 

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;typedef long long LL;const int N = 2e5+20, M = 4e4+10, mod = 1e9+7, inf = 0x3f3f3f3f;int c[N][2],mx[N],size[N],rev[N],fa[N],ID[N],t1,t2,id[N],n,m,rt,sz;LL v[N],tag[N],sum[N];inline void push_up(int k) {        int l = c[k][0], r = c[k][1];        sum[k] = sum[l] + sum[r] + v[k];        size[k] = size[l] + size[r] + 1;}inline void push_down(int k) {        int l = c[k][0], r = c[k][1], t = tag[k];        if(t) {            tag[k] = 0;            if(l) {tag[l] += t,v[l]+=t,sum[l]+=1LL*size[l]*t;}            if(r) {tag[r] += t,v[r]+=t,sum[r]+=1LL*size[r]*t;}        }}inline void rotate(int x,int &k) {        int y = fa[x], z = fa[y], l ,r;        push_down(z);        push_down(y);        push_down(x);        if(c[y][0] == x) l=0;else l=1;        r=l^1;        if(y == k) k = x;        else {if(c[z][0] == y) c[z][0] = x;else c[z][1] = x;}        fa[x]=z;        fa[y]=x;        fa[c[x][r]]=y;        c[y][l]=c[x][r];        c[x][r]=y;        push_up(y);        push_up(x);}inline void splay(int x,int &k) {        push_down(k);        while(x!=k) {            int y = fa[x], z = fa[y];            if(y!=k) {                if(c[y][0] == x ^ c[z][0] == y) rotate(x,k);                else rotate(y,k);            }            rotate(x,k);        }}inline void ask_befor(int k,int x){     push_down(k);     if(k==0)return;     if(ID[k]<=x){t1=k;ask_befor(c[k][1],x);}     else ask_befor(c[k][0],x); }inline void ask_after(int k,int x){    push_down(k);   if(k==0)return;   if(ID[k]>=x){t2=k;ask_after(c[k][0],x);}   else ask_after(c[k][1],x);}inline void update(int l,int r,int val) {        ask_befor(rt,l-1),ask_after(rt,r+1);        int x = t1, y = t2;        splay(x,rt);splay(y,c[x][1]);        int z = c[y][0];        tag[z] += val;        v[z] += val;        sum[z] +=1LL*val*size[z];}inline void query(int l,int r) {        ask_befor(rt,l-1), ask_after(rt,r+1);        int x = t1, y = t2;        splay(x,rt),splay(y,c[x][1]);        int z = c[y][0];        printf("%lld\n",sum[z]);}inline void ins(int &k,int ids,int val,int last) {        push_down(k);        if(k == 0) {            ++sz;            size[sz]=1;            k = sz;            v[k] = val;            sum[k] = val;            fa[k] = last;            ID[k] = ids;            return ;        }        if(ids < ID[k]) ins(c[k][0],ids,val,k);        else ins(c[k][1],ids,val,k);        push_up(k);}inline void Delet(int l,int r) {        ask_befor(rt,l-1), ask_after(rt,r+1);        int x = t1, y = t2;        splay(x,rt),splay(y,c[x][1]);        c[y][0] = 0;}int main() {        sz = 0;        ins(rt,-1,0,0);        ins(rt,100000001,0,rt);        scanf("%d",&n);        while(n--)        {           char ch[3];           int l,r,val;           scanf("%s%d%d",ch,&l,&r);           if(ch[0] == ‘I‘) {                ins(rt,l,r,rt);                splay(sz,rt);           } else if(ch[0] == ‘Q‘) {              query(l,r);           } else if(ch[0] == ‘M‘) {                scanf("%d",&val);                update(l,r,val);           } else if(ch[0] == ‘D‘) {                Delet(l,r);           }        }        return 0;}

 

hihocoder #1333 : 平衡树·Splay2


联系
我们