Hihocoder 1333 （splay）

Problem 平衡树 splay2

题目大意

　　维护一个序列，支持四种操作：

　　操作1：添加一个数，编号为x，权值为y。

　　操作2：删除编号在区间【x,y】内的数。

　　操作3：将编号在区间【x,y】内的数的权值增加为z。

　　操作4：询问编号在区间【x,y]内的数的权值和。

解题分析

　　由于增加了区间加和区间查询，所以要给每个增加一个lazy标记。

　　在每次搜索树的时候要对每个经过的节点进行一次pushdown，当树的形态或树的结点信息改变时要进行一次pushup。

参考程序

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 int tag=0;
  5 
  6 struct node{
  7     int id,num;
  8     long long lazy,val,sum;
  9     node *left,*right,*father;
 10     node(int id_=0,long long val_=0,int num_=0,long long lazy_=0,long long sum_=0,node* father_=NULL,node* left_=NULL,node* right_=NULL)
 11     {
 12         id=id_; val=val_; num=num_; lazy=lazy_; sum=sum_;
 13         father=father_; left=left_; right=right_;
 14     }
 15 }*rt,*t1,*t2;
 16 
 17 void search(node *now)
 18 {
 19     cout<<now->id; cout<<" val= "<<now->val<<" sum= "<<now->sum<<" num= "<<now->num<<" lazy= "<<now->lazy;
 20     if (now->left) cout<<" lson: "<<now->left->id;
 21     if (now->right) cout<<" rson: "<<now->right->id;
 22     cout<<endl;
 23     if (now->left) search(now->left);
 24     if (now->right) search(now->right);
 25 }
 26 
 27 void pushup(node* x)
 28 {
 29     x->sum=x->val; x->num=1;
 30     if (x->left)  x->sum+=x->left->sum,x->num+=x->left->num;
 31     if (x->right) x->sum+=x->right->sum,x->num+=x->right->num;
 32 }
 33 
 34 void pushdown(node* x)
 35 {
 36     if (x->lazy)
 37     {
 38         node *l = x->left,*r = x->right;
 39         if (l) 
 40         {
 41             l->lazy += x->lazy;
 42             l->val += x->lazy;
 43             l->sum += x->lazy * l->num;
 44         }
 45         if (r) 
 46         {
 47             r->lazy += x->lazy;
 48             r->val += x->lazy;
 49             r->sum += x->lazy * r->num;
 50         }
 51         x->lazy = 0;
 52     }
 53 }
 54 
 55 void right(node* x,node* &rt)
 56 {    
 57     node *y=x->father,*z=y->father;
 58     if (y==rt) rt=x; 
 59     else if (z->left==y) z->left=x; else z->right=x; //需要判断是左右孩子
 60     x->father=z; y->father=x; if (x->right) x->right->father=y;  //防止对空指针进行操作
 61     y->left=x->right; x->right=y; 
 62     pushup(y); pushup(x);
 63 }
 64 
 65 void left(node* x,node* &rt)
 66 {    
 67     node *y=x->father,*z=y->father;
 68     if (y==rt) rt=x; 
 69     else if (z->left==y) z->left=x; else z->right=x;  
 70     x->father=z; y->father=x; if (x->left) x->left->father=y;  
 71     y->right=x->left; x->left=y; 
 72     pushup(y); pushup(x);
 73 }
 74 
 75 void splay(node* x,node* &rt)
 76 {
 77     while (x!=rt)
 78     {    
 79         node *y=x->father, *z=y->father;
 80         if (y==rt)
 81         {
 82             if (x==y->left) right(x,rt);     
 83             else left(x,rt);
 84         }
 85         else
 86         {
 87             if (y==z->left)
 88                 if (x==y->left) { right(y,rt); right(x,rt); }
 89                 else { left(x,rt); right(x,rt); }
 90             else
 91                 if (x==y->right) { left(y,rt); left(x,rt); }
 92                 else { right(x,rt); left(x,rt); }
 93         }
 94     }
 95 }
 96 
 97 void insert(int id,int val,node* &now,node *last)
 98 {
 99     if (now==NULL)
100     {
101         now=new node(id,val,1,0,val,last);
102         splay(now,rt);
103         return;
104     }
105     pushdown(now);
106     if (id < now->id) insert(id,val,now->left,now); else  insert(id,val,now->right,now); 
107     //else还是要加的 返回的时候树的形态已经改变了
108 }
109 
110 void find_1(int id,node *x)
111 {
112     if (x==NULL) return;
113     pushdown(x);
114     if (x->id>=id) find_1(id,x->left); 
115     else {t1=x; find_1(id,x->right);} 
116 }
117 
118 
119 void find_2(int id,node *x)
120 {
121     if (x==NULL) return; 
122     pushdown(x);
123     if (x->id<=id) find_2(id,x->right); 
124     else {t2=x; find_2(id,x->left);} 
125 }
126 
127 void del(int l,int r)
128 {
129     t1=t2=NULL;
130     find_1(l,rt); splay(t1,rt);
131     find_2(r,rt->right); splay(t2,rt->right);
132     rt->right->left=NULL;
133     pushup(rt->right); pushup(rt);
134 }
135 
136 void add(int l,int r,int val)
137 {
138     t1=t2=NULL;
139     find_1(l,rt); splay(t1,rt);
140     find_2(r,rt->right); splay(t2,rt->right);
141     if (rt->right->left)
142     {
143         rt->right->left->lazy += val;
144         rt->right->left->sum += 1ll* val * rt->right->left->num;
145         rt->right->left->val += val;
146      }
147      pushup(rt->right); pushup(rt);
148 }
149 
150 long long query(int l,int r)
151 {
152     t1=t2=NULL;
153     find_1(l,rt); splay(t1,rt);
154     find_2(r,rt->right); splay(t2,rt->right);
155     if (rt->right->left)
156         return rt->right->left->sum;
157     else return 0;
158 }
159 
160 int main()
161 {
162     int n;
163     rt=NULL;
164     scanf("%d",&n);
165     insert(1<<30,0,rt,NULL); insert(-1<<30,0,rt,NULL);
166     for (int i=1;i<=n;i++)
167     {    
168         char s[3]; int x,y,z;
169         scanf("%s%d%d",s,&x,&y);
170         if (s[0]=='I') insert(x,y,rt,NULL); 
171         if (s[0]=='D') del(x,y);
172         if (s[0]=='M')
173         {
174             scanf("%d",&z);
175             add(x,y,z);
176         }
177         if (s[0]=='Q') cout<<query(x,y)<<endl;
178     }
179 }

View Code