SplayTree解决区间问题
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1754
题目大意：给出n个数，会动态的修改某个数，也会动态询问某区间内的最值。
思路：这是hdu上一道线段树入门的题目，也可以说是区间类数据结构的入门题目，再次
做这个题就是为了跟着notonlysuccess
进行splayTree的学习。利用splayTree解决这个问题
思路非常经典，splay(x,
y)操作可以将x节点旋转到y节点。利用这一性质，便可解决区间问题，就此题而言，我们要求的是[a，b]之间的最大值，也就是[a，b]区间上的一些信息，我们考虑这样的一些操作，首先通过二分将【1，n】共n个节点建立完全二叉树，然后将a-1这个节点旋转到根处，将b+1旋转到根的儿子处，那么此时此刻的b+1这个节点的左子树是什么？
非常清晰，正是【a，b】上的这些节点。
详细内容百度《运用伸展树解决数列维护问题》
提交情况： MLE
1次
忘记写析构函数了
2次
AC
code:
#include <cstdio>
#include <cstring>
#define maxn 1000000
#define _max(a, b) ((a) > (b) ? (a) :
(b))
intnum[maxn];
structsplayTreeNode{
int key, id, max,
number;
splayTreeNode* son[2], * father;
void init(int k, int nu,
int iid, splayTreeNode* left,
splayTreeNode* right, splayTreeNode* fa){
key = k, number = nu, id = iid, son[0] = left, son[1] = right,
father = fa;
}
};
structsplayTree{
#define root
nul->son[0]
splayTreeNode* nul, *link, *temp;
int ad;
splayTree(){
link = new
splayTreeNode[maxn];
ad = 0;
nul = &(link[ad ++]);
nul->init(0, 0, 0, NULL, NULL, NULL);
}
~splayTree(){ delete[] link;
}
int getMax(splayTreeNode* A,
splayTreeNode* B, splayTreeNode *C){
int max1 = (B == NULL) ? 0 :
B->max;
int max2 = (C == NULL) ? 0 :
C->max;
return _max(A->key,
_max(max1, max2));
}
void rotate(splayTreeNode*
&rt, int son1,
int son2){
splayTreeNode* temp = rt->son[son1];
rt->son[son1] =
temp->son[son2];
rt->max = getMax(rt, rt->son[0],
rt->son[1]);
if(temp->son[son2]
!= NULL){
temp->son[son2]->father =
rt;
temp->son[son2]->id =
son1;
}
temp->son[son2] = rt;
temp->father = rt->father;
temp->id
rt->id ;
rt->father = temp;
rt->id
temp->max = getMax(temp,
temp->son[0],
temp->son[1]);
rt = temp;
}
void splay(splayTreeNode* x,
splayTreeNode* rt){
if(x->father == rt
|| x == rt) return;
splayTreeNode* y = x->father,* z =
x->father->father;
if(z == rt){
if(y->son[0] == x)
rotate(z->son[y->id], 0,
1);
else
rotate(z->son[y->id], 1,
0);
}
else{
if(y->id
x->id ){
rotate(z->father->son[z->id],
x->id, (x->id)^1);
rotate(y->father->son[y->id],
x->id, (x->id)^1);
}
else{
rotate(y->father->son[y->id],
x->id, (x->id)^1);
rotate(z->father->son[z->id],
y->id, (y->id)^1);
}
}
splay(x, rt);
}
void built(splayTreeNode*
&rt, int l,
int r, int iid, splayTreeNode* rf){
if(l > r)
return;
int mid = (l + r) / 2;
rt = &(link[ad ++]);
rt->init(num[mid], mid, iid, NULL, NULL,
rf);
if(l == r){
rt->max = rt->key;
return;
}
built(rt->son[0], l, mid - 1, 0, rt);
built(rt->son[1],mid + 1, r, 1, rt);
rt->max = getMax(rt, rt->son[0],
rt->son[1]);
}
splayTreeNode* find(int k,
splayTreeNode* rt){
if(rt == NULL ||
rt->number == k) return rt;
if(k <
rt->number) return
find(k, rt->son[0]);
else return find(k,
rt->son[1]);
}
void updata(int a, int b,
splayTreeNode* rt){
if(rt == NULL) return;
if(rt->number ==
a){
rt->key = b;
rt->max = getMax(rt, rt->son[0],
rt->son[1]);
temp = rt;
return;
}
if(a <
rt->number) updata(a, b,
rt->son[0]);
else updata(a, b,
rt->son[1]);
rt->max = getMax(rt, rt->son[0],
rt->son[1]);
}
int answer(int a, int
b){
splayTreeNode* tempa, *tempb;
tempa = this->find(a
- 1, this->root);
tempb = this->find(b
+ 1, this->root);
if(tempa == NULL || tempb == NULL)
return -1;
this->splay(tempa,
this->nul);
this->splay(tempb,
this->root);
return
tempb->son[0]->max;
}
};
int main(){
char ord[2];
int a, b, n, m;
while(~scanf("%d %d", &n,
&m)){
splayTree spl;
for(int i = 1; i <= n; ++ i)
scanf("%d",
&num[i]);
spl.built(spl.root, 0, n + 1, 0, spl.nul);
while(m --){
scanf("%1s %d %d", ord,
&a, &b);
switch(ord[0]){
case 'U':
spl.updata(a, b, spl.root);
spl.splay(spl.temp, spl.nul);
break;
case 'Q':
printf("%d\n", spl.answer(a,
b));
break;
}
}
}
return 0;
}