【ZJOI2006】书架（Splay/树状数组+二分）

我们建棵平衡树，维护排名关系

TOP：将元素Splay到根，然后将左子树合并到该元素的后继

BOTTOM：将元素Splay到根，然后将右子树合并到该元素的前驱

（相当于强行更改偏序关系）

INSERT：直接与该元素的前驱/后继交换位置及信息

ASK：将元素Splay到根，输出左儿子的size

QUERY：第k大

一开始的插入由于是有序的，可以不用那么麻烦

#include<bits/stdc++.h>
const int N=80005;
using namespace std;
template<class T>
inline void read(T &x)
{
	x=0; int f=1;
	static char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
struct Tree
{
	int lc,rc,fa,size,val;
}t[N];
int n,m,id[N];
int root,tot;
inline int which(int u){return t[t[u].fa].rc==u;} 
inline void pushup(int u)
{
	t[u].size=t[t[u].lc].size+t[t[u].rc].size+1;
}
inline void Rotate(int u)
{
	int v=t[u].fa,w=t[v].fa;
	int b=(t[v].rc==u)?t[u].lc:t[u].rc;
	t[v].fa=u; t[u].fa=w;
	if(b) t[b].fa=v;
	if(w) (t[w].lc==v?t[w].lc:t[w].rc)=u;
	if(t[v].rc==u)	t[v].rc=b,t[u].lc=v;
	else t[v].lc=b,t[u].rc=v;
	pushup(v); pushup(u);
}
inline void Splay(int u,int tar)
{
	while(t[u].fa!=tar)
	{
		if(t[t[u].fa].fa!=tar)
		{
			if(which(u)==which(t[u].fa))	Rotate(t[u].fa);
			else Rotate(u);
		}
		Rotate(u);
	}
	if(!tar)	root=u;
}
inline void insert(int val)
{
	int u=++tot;
	t[root].rc=u; t[u].fa=root; t[u].val=val; t[u].size=1;
	Splay(u,0);
}
inline int find(int k)
{
	int u=root,ls=0;
	while(u)
	{
		if(ls+t[t[u].lc].size+1==k)	return u;
		if(k<=ls+t[t[u].lc].size) u=t[u].lc;
		else ls+=t[t[u].lc].size+1,u=t[u].rc;
	}
}
inline void Top(int u)
{
	u=id[u];
	Splay(u,0);
	if(!t[u].lc) return; 
	if(!t[u].rc) t[u].rc=t[u].lc,t[u].lc=0;
	else
	{
		int v=find(t[t[u].lc].size+2);
		t[t[u].lc].fa=v;
		t[v].lc=t[u].lc;
		t[u].lc=0;
		Splay(v,0);
	}
}
inline void Bottom(int u)
{
	u=id[u];
	Splay(u,0);
	if(!t[u].rc) return; 
	if(!t[u].lc) t[u].lc=t[u].rc,t[u].rc=0;
	else
	{
		int v=find(t[t[u].lc].size);
		t[t[u].rc].fa=v;
		t[v].rc=t[u].rc;
		t[u].rc=0;
		Splay(v,0);
	}
}
inline void Insert(int u,int f)
{
	if(!f) return;
	Splay(id[u],0);
	int v=find(f==1?t[t[id[u]].lc].size+2:t[t[id[u]].lc].size);
	int a=t[id[u]].val,b=t[v].val;
	swap(t[id[u]].val,t[v].val);
	swap(id[a],id[b]);
}
inline int Ask(int u)
{
	u=id[u];
	Splay(u,0);
	return t[t[u].lc].size;
}
int main()
{
	read(n),read(m);
	int v;
	read(v);
	root=++tot;
	id[v]=1; t[root].val=v; t[root].size=1;
	for(int i=2,x;i<=n;i++)
	{
		read(x);
		id[x]=i;
		insert(x);
	}
	char s[10];
	for(int i=1,x,f;i<=m;i++)
	{
		scanf("%s",s); read(x);
		if(s[0]=='T') Top(x);
		if(s[0]=='B') Bottom(x);
		if(s[0]=='I') read(f),Insert(x,f);
		if(s[0]=='A') write(Ask(x)),putchar('\n');
		if(s[0]=='Q') write(t[find(x)].val),putchar('\n');
	}
	return 0; 
}

当然，写这样一颗Splay+调出来会花掉我们很多很多时间，也要适当的学习一下水的方法以应对考试

这道题可以使用树状数组来水

建一个类似权值树状数组的东西，然后在前面后面都预留N个位置为Top/Bottom操作做准备，对于查询第k大配合二分即可

实验证明这个玩意跑的飞快,才100多ms

#include<bits/stdc++.h>
const int N=80000;
const int front=80000;
using namespace std;
int n,m,a[3*N+100],pos[3*N+100];
template<class T>
inline void read(T &x)
{
	x=0; int f=1;
	static char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
int tree[3*N+100];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int del) { for(;x<=3*N;x+=lowbit(x)) tree[x]+=del;}
inline int query(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x)) ans+=tree[x];
	return ans;
}
inline int kth(int k)
{
	int l=0,r=3*N,ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(query(mid)<=k) ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(a[ans]==0)
	{
		int p=ans;
		while(!a[p]) p--;
		return p;
	}
	return ans;
}
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) 
	{
		read(a[front+i]);
		pos[a[front+i]]=i+front;
	}
	for(int i=front+1;i<=front+n;i++) update(i,1);
	char s[10];
	int head=front+1,tail=front+n;
	for(int i=1,x,f;i<=m;i++)
	{
		scanf("%s",s); read(x);
		if(s[0]=='T')
		{
			head--;
			a[head]=x; a[pos[x]]=0;
			update(pos[x],-1);
			pos[x]=head;
			update(head,1);
		}
		if(s[0]=='B')
		{
			tail++;
			a[tail]=x; a[pos[x]]=0;
			update(pos[x],-1);
			pos[x]=tail;
			update(tail,1);
		} 
		if(s[0]=='I')
		{
			read(f);
			if(!f) continue;
			int size=query(pos[x]);
			int p=kth(size+f);
			int b=a[p];
			swap(a[p],a[pos[x]]);
			swap(pos[b],pos[x]);
		}
		if(s[0]=='A') write(query(pos[x])-1),putchar('\n');
		if(s[0]=='Q') write(a[kth(x)]),putchar('\n');
	}
	return 0;
}