题目描述
1. 加入：一个新的成员加入同好会，我会分配给他一个没有使用的id，并且询问他的兴趣值val。
2. 修改：id在区间[a,b]内的成员，兴趣值同时改变k，k有可能是负数，表示他们失去了对同好会的兴趣。
3. 退出：id在区间[a,b]内的成员要退出同好会，虽说是区间，也有可能只有1个人。
4. 询问：老师会问我在区间[a,b]内的成员总的兴趣值。
输入
第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
需注意的细节：
1.Delet Add rotate等地方要updata
2.insert rotate处标记要下移
3.size*mark时要转（Long Long）
4.关键是时时刻刻都要先pushdown再updata 和 rotate 不然会出错
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long ll; 10 const int N=200005,INF=10000001; 11 struct node 12 { 13 node *child[2],*fa; 14 int x,mark,size,val;long long sum; 15 }a[N]; 16 node *pos=a,*root,*newone; 17 void check(node *r); 18 void updata(node *&r) 19 { 20 if(r){ 21 r->sum=(r->child[0]?r->child[0]->sum:0)+(r->child[1]?r->child[1]->sum:0)+r->val; 22 r->size=(r->child[0]?r->child[0]->size:0)+(r->child[1]?r->child[1]->size:0)+1; 23 } 24 } 25 void pushdown(node *&r) 26 { 27 if(!r || !r->mark)return ; 28 if(r->child[0])r->child[0]->mark+=r->mark,r->child[0]->sum+=(ll)r->mark*r->child[0]->size,r->child[0]->val+=r->mark; 29 if(r->child[1])r->child[1]->mark+=r->mark,r->child[1]->sum+=(ll)r->mark*r->child[1]->size,r->child[1]->val+=r->mark; 30 updata(r); 31 r->mark=0; 32 } 33 void rotate(node *&r,bool t)//0left 1right 34 { 35 node *y=r->fa; 36 pushdown(y); 37 pushdown(r); 38 y->child[!t]=r->child[t]; 39 if(r->child[t])r->child[t]->fa=y; 40 if(y->fa)y->fa->child[y->fa->child[1]==y]=r; 41 r->fa=y->fa; 42 r->child[t]=y; 43 y->fa=r; 44 updata(r); 45 updata(y); 46 updata(r->fa); 47 } 48 void splay(node *r,node *g) 49 { 50 while(r->fa!=g) 51 { 52 if(r->fa->fa==g)rotate(r,r->fa->child[0]==r); 53 else 54 { 55 node *y=r->fa; 56 bool t=y->fa->child[0]==y; 57 if(y->child[t]==r)rotate(r,!t); 58 else rotate(y,t); 59 rotate(r,t); 60 } 61 } 62 if(g==NULL)root=r; 63 } 64 void newnode(node *&r,int key,int val,node *fa) 65 { 66 r=pos++; 67 r->fa=fa; 68 r->child[0]=r->child[1]=NULL; 69 r->x=key;r->val=val;r->mark=0;r->size=1;r->sum=val; 70 } 71 void insert(node *&r,int key,int val,node *fa) 72 { 73 if(r==NULL){ 74 newnode(r,key,val,fa); 75 splay(r,NULL); 76 return ; 77 } 78 else { 79 pushdown(r); 80 insert(r->child[key>r->x],key,val,r); 81 } 82 } 83 node *pre,*nxt; 84 void getpre(node *r,int key) 85 { 86 if(r==NULL)return ; 87 if(r->x>=key)getpre(r->child[0],key); 88 else pre=r,getpre(r->child[1],key); 89 } 90 void getnext(node *r,int key) 91 { 92 if(r==NULL)return ; 93 if(r->x<=key)getnext(r->child[1],key); 94 else nxt=r,getnext(r->child[0],key); 95 } 96 void work(int l,int r) 97 { 98 getpre(root,l);getnext(root,r); 99 splay(pre,NULL);splay(nxt,pre);100 updata(root->child[1]);updata(root);101 }102 void Delet(int l,int r)103 {104 work(l,r);105 root->child[1]->child[0]=NULL;106 updata(root->child[1]);updata(root);107 }108 void add(int l,int r,int to)109 {110 work(l,r);111 root->child[1]->child[0]->mark+=to;112 root->child[1]->child[0]->sum+=(ll)to*root->child[1]->child[0]->size;113 root->child[1]->child[0]->val+=to;114 updata(root->child[1]);updata(root);115 }116 long long ask(int l,int r)117 {118 work(l,r);119 node *y=root->child[1]->child[0];120 return y==NULL?0:y->sum;121 }122 void haha()123 {124 insert(root,-INF,0,NULL);125 insert(root,INF,0,NULL);126 }127 int main()128 {129 freopen("pp.in","r",stdin);130 freopen("pp.out","w",stdout);131 haha();132 int n;133 char ch;int x,y,z;134 scanf("%d",&n);135 while(n--)136 {137 scanf("\n%c%d%d",&ch,&x,&y);138 if(ch=='I')insert(root,x,y,NULL);139 if(ch=='D')Delet(x,y);140 if(ch=='M'){141 scanf("%d",&z);142 add(x,y,z);143 }144 if(ch=='Q')printf("%lld\n",ask(x,y));145 }146 return 0;147 }