终于把区间操作的Splay搞明白了……
Splay的大致框架是这样的：
【代码中的Zig-Zig和Zig-Zag操作其实是可以优化的，实际只需要3次passDown和3次update】
template <class T>
struct SplayNode
{
typedef SplayNode<T> Node;
Node* lch;
Node* rch;
Node* parent;
T val;
SplayNode(const T& _val,Node* _parent):
lch(),rch(),parent(_parent),val(_val) {}
void passDown() {}
void update() {}
void lRotate()
{
if(parent->parent)
{
if(parent==parent->parent->lch)
parent->parent->lch=this;
else parent->parent->rch=this;
}
parent->passDown();
passDown();
parent->rch=this->lch;
if(lch) lch->parent=this->parent;
lch=parent;
parent=parent->parent;
lch->parent=this;
lch->update();
update();
}
void rRotate()
{
if(parent->parent)
{
if(parent==parent->parent->lch)
parent->parent->lch=this;
else parent->parent->rch=this;
}
parent->passDown();
passDown();
parent->lch=this->rch;
if(rch) rch->parent=this->parent;
rch=parent;
parent=parent->parent;
rch->parent=this;
rch->update();
update();
}
Node* splay()
{
while(parent)
{
;
; ;
if(parent->parent)
{
;
;
}
switch(status)
{
: rRotate(); break;
: lRotate(); break;
: parent->rRotate(); this->rRotate(); break;
: lRotate(); rRotate(); break;
: rRotate(); lRotate(); break;
: parent->lRotate(); this->lRotate(); break;
}
}
return this;
}
};
注意双旋的Zig-Zig（Zag-Zag）和Zig-Zag（Zag-Zig），后者可以分解成两次单旋，而前者不能。
借教室一题的85分代码（Vijos）：
（Splay果然常数大……当然很可能是我写萎了……）
#include <algorithm>
using std::max;
using std::min;
struct SplayNode
{
typedef SplayNode Node;
Node* lch;
Node* rch;
Node* parent;
int idx;
int val;
int minVal;
int lazyTag;
SplayNode() {}
SplayNode(int _idx,int _val,Node* _parent):
lch(),rch(),parent(_parent),idx(_idx),val(_val),
minVal(_val),lazyTag() {}
void assign(int _idx,int _val,int _minVal,Node* _rch,Node* _parent)
{
idx=_idx;
val=_val;
minVal=_minVal;
lazyTag=;
lch=;
rch=_rch;
parent=_parent;
}
int actual() { return minVal + lazyTag; }
void passDown()
{
if(!lazyTag) return;
if(lch) lch->lazyTag += this->lazyTag;
if(rch) rch->lazyTag += this->lazyTag;
val += lazyTag;
minVal += lazyTag;
lazyTag = ;
}
void update()
{
minVal = lch ?
( rch ? min(min(lch->actual(),rch->actual()),this->val) :
min(lch->actual(),this->val) ) :
( rch ? min(rch->actual(),this->val) : this->val );
}
void lRotate()
{
if(parent->parent)
{
if(parent==parent->parent->lch)
parent->parent->lch=this;
else parent->parent->rch=this;
}
parent->passDown();
passDown();
parent->rch=this->lch;
if(lch) lch->parent=this->parent;
lch=parent;
parent=parent->parent;
lch->parent=this;
lch->update();
update();
}
void rRotate()
{
if(parent->parent)
{
if(parent==parent->parent->lch)
parent->parent->lch=this;
else parent->parent->rch=this;
}
parent->passDown();
passDown();
parent->lch=this->rch;
if(rch) rch->parent=this->parent;
rch=parent;
parent=parent->parent;
rch->parent=this;
rch->update();
update();
}
Node* splay()
{
while(parent)
{
;
; ;
if(parent->parent)
{
;
;
}
switch(status)
{
: rRotate(); break;
: lRotate(); break;
: parent->rRotate(); this->rRotate(); break;
: lRotate(); rRotate(); break;
: rRotate(); lRotate(); break;
: parent->lRotate(); this->lRotate(); break;
}
}
return this;
}
};
;
SplayNode node[maxN];
int n,m;
int change(int d,int s,int t)
{
;
) status |= ;
;
switch(status)
{
:
node[s-].splay();
node[s-].rch->parent=;
node[t+].splay();
node[s-].rch=&node[t+];
node[t+].parent=&node[s-];
node[t+].lch->lazyTag -= d;
node[t+].update();
node[s-].update();
;
:
node[t+].splay();
node[t+].lch->lazyTag -= d;
node[t+].update();
;
:
node[s-].splay();
node[s-].rch->lazyTag -= d;
node[s-].update();
;
:
node[].splay();
node[].val -= d;
node[].minVal -= d;
].rch) node[].rch->lazyTag -= d;
;
}
}
#include <cstdarg>
#include <cstdio>
#include <cctype>
void readInt(int argCnt,...)
{
va_list va;
va_start(va,argCnt);
while(argCnt--)
{
int* dest=va_arg(va,int*);
;
char curDigit;
do curDigit=getchar(); while(!isdigit(curDigit));
while(isdigit(curDigit))
{
destVal = destVal * + curDigit - ';
curDigit=getchar();
}
*dest=destVal;
}
va_end(va);
}
int avai[maxN];
int main()
{
readInt(,&n,&m);
;i<=n;++i) readInt(,avai+i);
for(int i=n;i;--i)
{
,&node[i-]);
) node[i].assign(n,avai[i],min(avai[i],node[i+].minVal),&node[i+],);
].minVal),&node[i+],&node[i-]);
}
;i<=m;i++)
{
int d,s,t;
readInt(,&d,&s,&t);
int rt=change(d,s,t);
)
{
printf("-1\n%d",i);
;
}
}
printf(");
;
}
修正了一点失误+改成了静态内存
（也许出题人没想到有人会用splay写这道题，所以之前的错误居然没被查出来……）
对于这道题，我们需要给每个Node额外设立3个域：idx（教室的标号，作为键值），minVal（子树中val的最小值），和lazyTag（修改的懒惰标记）
对区间[L,R]进行修改时，首先将L-1提到根，然后将R+1提到根的右孩子处，那么R+1的左孩子就是待修改的区间
当然要特判L==1和R==n（即左/右端为边界的情况）
注意旋转过程中要不断下传lazyTag并对节点的minVal值更新
（这个超级麻烦，一定要把每个细节都想全了，稍有一点疏忽就会出错，而且很不好查）
询问时直接询问根节点的minVal值即可（注意要让根节点的lazyTag传下去）
