题面：
#1333 : 平衡树·Splay2
描述
小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 链接：http://hihocoder.com/problemset/problem/1333 代码：#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll M = 2e5+;
const ll inf = 0x3f3f3f;
ll n,sz,rt,t1,t2;
ll c[M][],sum[M],fa[M],id[M],tag[M],v[M],siz[M];
inline void pushup(ll k){
ll l = c[k][],r = c[k][];
sum[k] = sum[l] + sum[r] + v[k];
siz[k] = siz[l] + siz[r] + ;
} void pushdown(ll k){
ll l = c[k][],r = c[k][],t = tag[k];
if(t){
tag[k] = ;
if(l) tag[l]+=t,sum[l]+=t*siz[l],v[l]+=t;
if(r) tag[r]+=t,sum[r]+=t*siz[r],v[r]+=t;
}
} void rotate(ll x,ll &k){
ll y = fa[x],z = fa[y],l,r;
if(c[y][] == x) l = ;
else l = ;
r = l^;
if(y == k) k = x;
else {
if(c[z][]==y) c[z][]=x;
else c[z][] = x;
}
fa[x] = z;fa[y] = x;fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
pushup(y); pushup(x);
} void splay(ll x,ll &k){
while(x != k){
ll y = fa[x],z = fa[y];
if(y != k){
if(c[y][]==x^c[z][]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
} inline void ask_befor(ll k,ll x){
pushdown(k);
if(k == ) return ;
if(id[k] <= x) {
t1 = k;
ask_befor(c[k][],x);
}
else ask_befor(c[k][],x);
} inline void ask_after(ll k,ll x){
pushdown(k);
if(k == ) return ;
if(id[k] >= x) {
t2 = k;
ask_after(c[k][],x);
}
else ask_after(c[k][],x);
} inline void ins(ll &k,ll idx,ll val,ll last){
pushdown(k);
if(k == ){
++sz;
siz[sz] = ;
k = sz;
v[k] = val;
sum[k] = val;
fa[k] = last;
id[k] = idx;
return ;
}
if(idx < id[k]) ins(c[k][],idx,val,k);
else ins(c[k][],idx,val,k);
pushup(k);
} inline void update(ll l,ll r,ll val){
ask_befor(rt,l-);ask_after(rt,r+);
ll x = t1,y = t2;
splay(x,rt); splay(y,c[x][]);
ll z = c[y][];
tag[z] += val;v[z] += val; sum[z] += val*siz[z];
} void del(ll l,ll r){
ask_befor(rt,l-);ask_after(rt,r+);
ll x = t1,y = t2;
splay(x,rt); splay(y,c[x][]);
c[y][] = ;
} inline void query(ll l,ll r){
ask_befor(rt,l-);ask_after(rt,r+);
ll x = t1,y = t2;
splay(x,rt); splay(y,c[x][]);
ll z = c[y][];
printf("%lld\n",sum[z]);
} int main()
{
sz = ;
ins(rt,-,,);
ins(rt,,,rt);
scanf("%lld",&n);
for(ll i = ;i <= n;i ++){
ll l,r,val;
string s;
cin>>s;
//cout<<s[0]<<endl;
scanf("%lld%lld",&l,&r);
if(s[] == 'M') scanf("%lld",&val),update(l,r,val);
else if(s[] == 'I') ins(rt,l,r,rt),splay(sz,rt);
else if(s[] == 'Q') query(l,r);
else del(l,r);
}
return ;
}