平衡树总结

平衡树

普通平衡树

得了，平衡树的基本操作我怎么会自己写呢？详见http://www.cnblogs.com/cjyyb/p/7499020.html

文艺平衡树

功能：序列反转
实现：把序列右端点转到Splay左端点上面，同时打个懒标记，到时候（kth和write）转即可。
注意：1.两个边界节点1和n+2防死循环
2.注意到数的位置与它的大小没什么关系，我们应维护的是数的位置而非一般而言的权值。
3.可以给每个节点打一个懒标记mk，若要转两次就抵消。
4.每个点唯一。
5.中序遍历输出。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
int n,m,k,root,tot;
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
struct node
{
  int z[2],fa,w,sz,mk;
}t[N];
il void pushup(re int x)
{
  t[x].sz=t[t[x].z[0]].sz+t[t[x].z[1]].sz+1;
}
il void pushdown(re int x)
{
  if(t[x].mk)
    {
      t[t[x].z[0]].mk^=1;
      t[t[x].z[1]].mk^=1;
      t[x].mk=0;
      swap(t[x].z[0],t[x].z[1]);
    }
}
il void rotate(re int x)
{
  re int y=t[x].fa,z=t[y].fa,k=t[y].z[1]==x;
  t[z].z[t[z].z[1]==y]=x;//x到y的位置
  t[x].fa=z;
  t[y].z[k]=t[x].z[k^1];//y的儿子变为x的相对儿子
  t[t[x].z[k^1]].fa=y;
  t[x].z[k^1]=y;//x的相对儿子变为y
  t[y].fa=x;
  pushup(y);pushup(x);
}
il void Splay(re int x,re int tar)
{
  while(t[x].fa!=tar)
    {
      re int y=t[x].fa,z=t[y].fa;
      if(z!=tar) (t[z].z[1]==y)^(t[y].z[1]==x)?rotate(x):rotate(y);
      rotate(x);
    }
  if(!tar) root=x;
}
il void insert(re int x)
{
  re int u=root,fa=0;
  while(u&&t[u].w!=x) fa=u,u=t[u].z[x>t[u].w];
  u=++tot;
  if(fa) t[fa].z[x>t[fa].w]=u;
  t[tot].z[0]=t[tot].z[1]=0;
  t[tot].sz=1;
  t[tot].w=x;t[tot].fa=fa;
  Splay(u,0);
}
il int kth(re int k)
{
  re int u=root;
  while(233)
    {
      pushdown(u);
      if(t[t[u].z[0]].sz>=k) u=t[u].z[0];
      else if(t[t[u].z[0]].sz+1==k) return u;
      else k-=t[t[u].z[0]].sz+1,u=t[u].z[1];//由于为编号排序，每个点唯一
    }
}
il void work(re int l,re int r)
{
  l=kth(l);r=kth(r+2);
  Splay(l,0);Splay(r,l);
  t[t[t[root].z[1]].z[0]].mk^=1;//mk的本质是一种懒标记，若要转两次就抵消???
}
il void write(re int x)
{
  pushdown(x);
  if(t[x].z[0]) write(t[x].z[0]);
  if(t[x].w>1&&t[x].w<n+2) printf("%d ",t[x].w-1);
  if(t[x].z[1]) write(t[x].z[1]);//中序遍历
}
int main()
{
  n=gi();m=gi();
  fp(i,1,n+2) insert(i);//1和n+2是空的边界，防止死循环
  while(m--)
    {
      re int l=gi(),r=gi();
      work(l,r);
    }
  write(root);printf("\n");
  return 0;
}