题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3223
代码1（TOP-DOWN非递归）（第一次打这种带修改标记的splay，调的快吐了。。）
(速度挺慢：
5bafa40f4bfbfbed8be5d2547af0f736afc31f58.jpg.png
)：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
struct node {
node *left,*right;
int s,k;
bool flag;
node () {
flag=false;
}
};
node *roof,*bank=new(node);
int n,m;
void Putdown(node *t) {
if (t!=bank&&t->flag) {
swap(t->left,t->right);
t->left->flag^=true;
t->right->flag^=true;
t->flag=false;
}
}
void RepairS(node *t) {
t->s=t->left->s+t->right->s+1;
}
void zag(node* &t) {
if (t->flag) Putdown(t);
node *k=t->right;
if (k->flag) Putdown(k);
t->right=k->left;
RepairS(t);
k->left=t;
RepairS(k);
t=k;
}
void zig(node* &t) {
if (t->flag) Putdown(t);
node *k=t->left;
if (k->flag) Putdown(k);
t->left=k->right;
RepairS(t);
k->right=t;
RepairS(k);
t=k;
}
void Merge(node *u,node* &t,bool flag) {
if (u->flag) Putdown(u);
if (!t) t=u
; else {
if (flag) {
t->left=u;
RepairS(t);
zig(t);
} else {
t->right=u;
RepairS(t);
zag(t);
}
}
}
void splay(int s,node* &t) {
node *l=NULL,*r=NULL;
if (t->flag) Putdown(t);
while (t!=bank&&t->left->s!=s) {
if (t->flag) Putdown(t);
if (t->left->flag) Putdown(t->left);
if (t->right->flag) Putdown(t->right);
if (s<t->left->s) {
if (t->left->flag) Putdown(t->left);
if (t->right->flag) Putdown(t->right);
if (s<t->left->left->s) {
zig(t);
}
if (t->flag) Putdown(t);
if (t->left->flag) Putdown(t->left);
if (t->right->flag) Putdown(t->right);
node *u=t->left;
t->left=bank;
RepairS(t);
Merge(t,r,true);
t=u;
} else {
if (t->flag) Putdown(t);
if (t->left->flag) Putdown(t->left);
if (t->right->flag) Putdown(t->right);
if (s-(t->left->s+1)>t->right->left->s+1) {
zag(t);
}
if (t->flag) Putdown(t);
if (t->left->flag) Putdown(t->left);
if (t->right->flag) Putdown(t->right);
s-=(t->left->s+1);
node *u=t->right;
t->right=bank;
RepairS(t);
Merge(t,l,false);
t=u;
}
}
if (t->flag) Putdown(t);
if (t->left->flag) Putdown(t->left);
if (t->right->flag) Putdown(t->right);
if (l) {
if (l->flag) Putdown(l);
node *u=t->left;
t->left=l;
l->right=u;
RepairS(l);
RepairS(t);
}
if (r) {
if (r->flag) Putdown(r);
node *u=t->right;
t->right=r;
r->left=u;
RepairS(r);
RepairS(t);
}
}
void Print(node *t) {
if (t==bank) return ;
if (t->flag) Putdown(t);
Print(t->left);
if (t->k>0&&t->k<=n) printf("%d ",t->k);
Print(t->right);
}
int main() {
roof=bank->left=bank->right=bank;
bank->s=0;
scanf("%d%d",&n,&m);
for (int i=0;i<=n+1;i++) {
node *t=roof,*T=NULL;
while (t!=bank) {
T=t;
t->s++;
t=t->right;
}
t=new(node);
t->left=t->right=bank;
t->s=1;
t->k=i;
if (T) {
T->right=t;
} else roof=t;
splay(i,roof);
}
while (m--) {
int l,r;
scanf("%d%d",&l,&r);
splay(l-1,roof);
splay(r-roof->left->s,roof->right);
roof->right->left->flag^=true;
}
Print(roof);
return 0;
}
代码2（自底向上，递归版）（比起前面的代码简短高效多了，而且只有70行左右，不维护父节点域，很好写~，速度勉勉强强（加了IO优化）：
902397dda144ad34c23b62acd2a20cf431ad8511.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
#define L(t) T[t].left
#define R(t) T[t].right
#define K(t) T[t].key
#define S(t) T[t].size
#define F(t) T[t].flag
#define repairS(t) S(t)=S(L(t))+S(R(t))+1
#define Cl(r,t)(S(L(t))>r)
struct node{
int left,right,size,key;
bool flag;
node(){left=right=size=flag=0;}
} T[MAXN];
int n,m,v=0,roof=0;
node make(int _s,int _k){node u;u.size=_s,u.key=_k;return u;}
void pushdown(int t){
if(F(t)&&t)
{swap(L(t),R(t));F(t)=false,F(L(t))^=true,F(R(t))^=true;}
}
void zag(int&t){
pushdown(t);pushdown(R(t));
int k=R(t); R(t)=L(k);repairS(t);L(k)=t;repairS(k);t=k;
}
void zig(int&t){
pushdown(t);pushdown(L(t));
int k=L(t);L(t)=R(k);repairS(t);R(k)=t;repairS(k);t=k;
}
bool splay(int r,int&t,bool flag){
pushdown(t);
if(S(L(t))==r)return false;
bool w=splay(Cl(r,t)?r:r-S(L(t))-1,Cl(r,t)?L(t):R(t),true);
if(w){
if(Cl(r,t)){
pushdown(L(t));
if(Cl(r,L(t))) zig(t),zig(t);else{zag(L(t));zig(t);}
}else{
pushdown(R(t));
if(!Cl(r-S(L(t))-1,R(t))) zag(t),zag(t);else{zig(R(t));zag(t);}
}
}else if(!flag){if(Cl(r,t)) zig(t);else zag(t);}
return w^true;
}
void Insert(int k,int&t){
if(!t){T[t=++v]=make(1,k);return;}S(t)++;Insert(k,R(t));
}
void Print(int t){
pushdown(t);if(L(t)) Print(L(t));
if(K(t)!=n+1&&K(t)) printf("%d ",K(t));
if(R(t)) Print(R(t));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++){Insert(i,roof);splay(i,roof,false);}
while(m--){
int l,r;scanf("%d%d",&l,&r);
splay(l-1,roof,false);splay(r-S(L(roof)),R(roof),false);
F(L(R(roof)))^=true;
}
Print(roof);
return 0;
}
代码3：
adaf2edda3cc7cd9dd6326f53b01213fb80e914b.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
#define L(t) T[t].left
#define R(t) T[t].right
#define K(t) T[t].key
#define S(t) T[t].size
#define F(t) T[t].flag
#define repairS(t) S(t)=S(L(t))+S(R(t))+1
#define Cl(r,t) (S(L(t))>r)
struct node {
int left,right,size,key;
bool flag;
node(){left=right=size=0;flag=false;}
} T[MAXN];
int n,m,v=0,roof=0;
node make(int _s,int _k){node u;u.size=_s,u.key=_k;return u;}
void pushdown(int t) {
if (F(t)&&t){swap(L(t),R(t));F(t)=false,F(L(t))^=true,F(R(t))^=true;}
}
void zag(int &t) {
pushdown(t);pushdown(R(t));
int k=R(t);R(t)=L(k);repairS(t);
L(k)=t;repairS(k);t=k;
}
void zig(int &t) {
pushdown(t);pushdown(L(t));
int k=L(t);L(t)=R(k);repairS(t);
R(k)=t;repairS(k);t=k;
}
void splay(int r,int &t) {
pushdown(t);
while (S(L(t))!=r) {
if (Cl(r,t)) {
pushdown(L(t));
if (S(L(L(t)))==r){zig(t);break;}
if (Cl(r,L(t)))zig(L(t));else zag(L(t));
zig(t);
} else {
pushdown(R(t));
if (S(L(R(t)))==r-S(L(t))-1){zag(t);break;}
if (!Cl(r-S(L(t))-1,R(t)))zag(R(t));else zig(R(t));
zag(t);
}
}
}
void Insert(int k,int &t) {
if (!t){T[t=++v]=make(1,k);return ;}
S(t)++;Insert(k,R(t));
}
void Print(int t) {
pushdown(t);
if (L(t)) Print(L(t));
if (K(t)!=n+1&&K(t)) printf("%d ",K(t));
if (R(t)) Print(R(t));
}
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i<=n+1;i++) {
Insert(i,roof);
splay(i,roof);
}
while (m--) {
int l,r;
scanf("%d%d",&l,&r);
splay(l-1,roof),splay(r-S(L(roof)),R(roof));
F(L(R(roof)))^=true;
}
Print(roof);
return 0;
}
网友评论