hdu 4441 Queue Sequence (splay + 线段树)
2014-03-19 13:17:18         来源：hdu 4441 Queue Sequence (splay + 线段树)

```#include
#include
#include
#include
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 200005
#define inf 0x3f3f3f3f
#define keyTree (ch[ch[root][1]][0])

using namespace std;
typedef long long LL;

int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn];
int root,top1,top2;
int val[maxn],a[maxn];
int pos1[maxn],pos2[maxn];
LL sum[maxn];
int z[maxn],f[maxn],m;

void Treaval(int x)
{
if(x)
{
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d , sum = %2lld z = %d f=%d\n",x,ch[x][0],ch[x][1],pre[x],siz[x],val[x],sum[x],z[x],f[x]);
Treaval(ch[x][1]);
}
}
void debug()
{
printf("root=%d\n",root);
Treaval(root);
}

void New(int &x,int PRE,int v)
{
x=++top1;

ch[x][0]=ch[x][1]=0;
siz[x]=1;
pre[x]=PRE;

val[x]=v;
sum[x]=v;
z[x]=v>0;
f[x]=v<0;
}
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+(LL)val[x];
z[x]=z[ch[x][0]]+z[ch[x][1]]+(val[x]>0);
f[x]=f[ch[x][0]]+f[ch[x][1]]+(val[x]<0);
}

void Rotate(int x,int kind)
{
int y=pre[x];

ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
pushup(y);
}
void Splay(int x,int goal)
{
while(pre[x]!=goal)
{
if(pre[pre[x]]==goal)
Rotate(x,ch[pre[x]][0]==x);
else
{
int y=pre[x];
int kind=ch[pre[y]][0]==y;
if(ch[y][kind]==x){
Rotate(x,!kind);
Rotate(x,kind);
}
else {
Rotate(y,kind);
Rotate(x,kind);
}
}
}
pushup(x);
if(goal==0)root=x;
}

void RotateTo(int k,int goal)
{
int r=root;
while(siz[ch[r][0]]+1!=k)
{
if(k<=siz[ch[r][0]])
{
r=ch[r][0];
}
else
{
k-=siz[ch[r][0]]+1;
r=ch[r][1];
}
}
Splay(r,goal);
}

void init()
{
root=top1=top2=0;
ch[0][0]=ch[0][1]=siz[0]=pre[0]=0;

New(root,0,0);
New(ch[root][1],root,0);

siz[root]=2;
pushup(ch[root][1]);
pushup(root);
}

int tre[maxn<<2];
void push_up(int num)
{
tre[num]=min(tre[num<<1],tre[num<<1|1]);
}
void build(int num,int s,int e)
{
if(s==e)
{
tre[num]=s;
return;
}
int mid=(s+e)>>1;
build(lson);
build(rson);
push_up(num);
}

void update(int num,int s,int e,int pos,int val)
{
if(s==e)
{
tre[num]=val?inf:s;
return;
}
int mid=(s+e)>>1;
if(pos<=mid)update(lson,pos,val);
else update(rson,pos,val);
push_up(num);
}
int Splay_insert(int pos,int v)
{
RotateTo(pos,0);
RotateTo(pos+1,root);

New(keyTree,ch[root][1],v);
pushup(ch[root][1]);
pushup(root);
return keyTree;
}
int kth(int x,int n)
{
int ls=ch[x][0],rs=ch[x][1];
if(f[ls]==n && val[x]<0){Splay(x,0);return siz[ch[root][0]];}
else if(f[ls]>n)return kth(ls,n);
else return kth(rs,n-f[ls]-(val[x]<0));
}

void remove(int x)
{
Splay(pos1[x],0);
int P=siz[ch[root][0]];
RotateTo(P,0);
RotateTo(P+2,root);
keyTree=0;
pushup(ch[root][1]);
pushup(root);

Splay(pos2[x],0);
P=siz[ch[root][0]];
RotateTo(P,0);
RotateTo(P+2,root);
keyTree=0;
pushup(ch[root][1]);
pushup(root);
}
void insert(int pos)
{
int num=tre[1];

pos1[num]=Splay_insert(pos+1,num);

Splay(pos1[num],0);

int n=z[ch[root][0]];

if(f[root]<=n)
{
int t=siz[root]-2+1;
pos2[num]=Splay_insert(t,-num);
}
else
{
int t=kth(root,n);
pos2[num]=Splay_insert(t,-num);
}
update(1,1,m,num,1);
}

int main()
{
int cas=1;

while(scanf("%d",&m)!=EOF)
{
printf("Case #%d:\n",cas++);
init();
build(1,1,m);

for(int sss=1;sss<=m;sss++)
{
// cout<

```