LBN好神啊~~暑假里讲了一个晚上的平衡树。。。虽然苯宝宝坚信自己写过一次BZOJ1588，然而程序丢失得一干二净。。。窝只能重新来惹

坑坑坑

BZOJ-1588 Splay模板题

[HNOI2002]营业额统计

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define NN 50010
#define INF 0x3f3f3f3f
using namespace std;

int root=0,n,ans=0,tree[NN][3],fa[NN],num[NN],tmp1,tmp2,size;

inline void rotate(int xx,int &k)
{
	int yy=fa[xx],zz=fa[yy],l,r;
	if (tree[yy][0]==xx) l=0; else l=1; r=l^1;
	if (yy==k) k=xx;
	else
	{	if (tree[zz][0]==yy) tree[zz][0]=xx; else tree[zz][1]=xx;}
	fa[xx]=zz, fa[yy]=xx, fa[tree[xx][r]]=yy;
	tree[yy][l]=tree[xx][r]; tree[xx][r]=yy;
}

inline void Splay(int xx,int &k)
{
	int yy,zz;
	while (xx!=k)
	{
		yy=fa[xx], zz=fa[yy];
		if (yy!=k)
		{
			if ((tree[yy][0]==xx)^(tree[zz][0]==yy)) rotate(xx,k);
			else rotate(yy,k);
		}
		rotate(xx,k);
	}
}

inline void Abefore(int &k,int xx)
{
	if (k==0) return;
	if (xx>=num[k]) tmp1=num[k], Abefore(tree[k][1],xx);
	else Abefore(tree[k][0],xx);
}
inline void Aafter(int &k,int xx)
{
	if (k==0) return;
	if (num[k]>=xx) tmp2=num[k], Aafter(tree[k][0],xx);
	else Aafter(tree[k][1],xx);
}

inline void Insert(int &k,int xx,int la)
{
	if (k==0)
	{size++, k=size, num[k]=xx, fa[k]=la, Splay(k,root); return;}
	if (xx<num[k]) Insert(tree[k][0],xx,k);
	else Insert(tree[k][1],xx,k);	
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	{
		int x;
		if (scanf("%d",&x)==EOF) x=0;
		tmp1=-INF, tmp2=INF;
		Abefore(root,x), Aafter(root,x);
		if (i==1) ans+=x;
		else ans+=min(x-tmp1,tmp2-x);
		Insert(root,x,0);
	}
	printf("%d\n",ans);
	return 0;
}

BZOJ-3224

Tyvj 1728 普通平衡树

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
#define NN 100100
using namespace std;
int t[NN][2],num[NN],sum[NN],fa[NN],cnt[NN],root=0,tot=0,n;
inline void rotate(int k)
{
	int tmp=fa[k],y=fa[tmp],x=(t[tmp][1]==k);
	fa[t[tmp][x]=t[k][x^1]]=tmp;
	fa[t[k][x^1]=tmp]=k;
	fa[k]=y;
	if (y) t[y][t[y][1]==tmp]=k;
	sum[tmp]=sum[t[tmp][0]]+sum[t[tmp][1]]+cnt[tmp];
}

inline void Splay(int xx,int k)
{
	for (int i;((i=fa[xx])!=k);rotate(xx))
		if (fa[i]!=k) rotate((t[i][0]==xx)==(t[fa[i]][0]==i)?i:xx);
	if (k==0) root=xx;
	sum[xx]=sum[t[xx][0]]+sum[t[xx][1]]+cnt[xx];
}
inline void Insert(int k,int xx)
{
	if (k==0) 
	{ root=k=++tot, num[k]=xx, fa[k]=t[k][0]=t[k][1]=0, sum[k]=cnt[k]=1; return;}
	while (k)
	{
		sum[k]++;
		if (xx==num[k]) { cnt[k]++; return;	}
		int &y=t[k][xx>=num[k]];
		if (y==0)
		{y=++tot, num[y]=xx,fa[y]=k,t[y][0]=t[y][1]=0,sum[y]=cnt[y]=1;k=y; break;}
		k=y;
	}
	Splay(k,0);
}
inline void Del(int k,int xx)
{
	while (k)
	{
		sum[k]--;
		if (num[k]==xx)	{cnt[k]--; break;}
		int &y=t[k][xx>=num[k]];
		k=y;
	}
	if (cnt[k]!=0) return;
	Splay(k,0);
	if (t[k][0]==0) {root=t[k][1]; fa[root]=0; return;}
	if (t[k][1]==0) {root=t[k][0]; fa[root]=0; return;}
	k=t[root][0];
	while (k)
	{
		int &y=t[k][1];
		if (y==0) break;
		k=y;
	}
	Splay(k,root);
	t[k][1]=t[root][1], fa[t[k][1]]=k, sum[k]=sum[root]-1, fa[k]=0, root=k;
	return;
}
inline int rank(int k,int xx)
{
	int tmp=0, ans;
	while (k)
	{
		if (xx>num[k]) tmp+=sum[t[k][0]]+cnt[k], k=t[k][1];
		else
		{
			if (xx==num[k]) return tmp+sum[t[k][0]]+1;
			k=t[k][0];
		}
	}
	return tmp;
}
inline int kth(int k,int xx)
{
	while (k)
	{
		if (xx>=sum[t[k][0]]+1 && xx<=sum[t[k][0]]+cnt[k]) return num[k];
		if (xx>sum[t[k][0]]+cnt[k]) { xx-=sum[t[k][0]]+cnt[k]; k=t[k][1];}
		else k=t[k][0];
	}
}
inline int pre(int k,int xx)
{
	int ans=0;
	while (k)
	{	if (num[k]<xx) ans=num[k], k=t[k][1]; else k=t[k][0];}
	return ans;
}
inline int suc(int k,int xx)
{
	int ans=0;
	while (k)
	{	if (num[k]>xx) ans=num[k], k=t[k][0]; else k=t[k][1];}
	return ans;
}
int main()
{
	scanf("%d",&n);
	while (n--)
	{
		int type,x;
		scanf("%d%d",&type,&x);
		if (type==1) Insert(root,x);
		else if (type==2) Del(root,x);
		else if (type==3) printf("%d\n",rank(root,x));
		else if (type==4) printf("%d\n",kth(root,x));
		else if (type==5) printf("%d\n",pre(root,x));
		else if (type==6) printf("%d\n",suc(root,x));
	}
	return 0;
}

BZOJ-1208

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define LL long long 
#define NN 80010
#define mod 1000000
using namespace std;
int n,size,root,kind,tmp1,tmp2,tree[NN][2],num[NN],fa[NN];
LL ans;

void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l,r;
    if(tree[y][0]==x)l=0;else l=1;r=l^1;
    if(y==k)k=x;
    else{if(tree[z][0]==y)tree[z][0]=x;else tree[z][1]=x;}
    fa[x]=z;fa[y]=x;fa[tree[x][r]]=y;
    tree[y][l]=tree[x][r];tree[x][r]=y;
}
inline void Splay(int xx,int &k)
{
	int y,z;
	while (xx!=k)
	{
		y=fa[xx], z=fa[y];
		if (y!=k)
		{
			if ((tree[y][0]==xx)^(tree[z][0]==y)) rotate(xx,k);	else rotate(y,k);
		}
		rotate(xx,k);
	}
}
inline void Del(int xx)
{
	Splay(xx,root);
	if (tree[xx][0]*tree[xx][1]==0) root=tree[xx][0]+tree[xx][1];
	else
	{
		int k=tree[xx][1];
		while (tree[k][0]) k=tree[k][0];
		tree[k][0]=tree[xx][0], fa[tree[xx][0]]=k;
		root=tree[xx][1];
	}
	fa[root]=0;
}
inline void Insert(int &k,int xx,int la)
{
	if (k==0) 
	{ k=++size, num[k]=xx, fa[k]=la, Splay(k,root); return;}
	if (xx<num[k]) Insert(tree[k][0],xx,k); else Insert(tree[k][1],xx,k);
}
inline void Aafter(int k,int xx)
{
	if (k==0) return;
	if (num[k]>=xx) tmp2=k, Aafter(tree[k][0],xx);
	else Aafter(tree[k][1],xx);
}
inline void Abefore(int k,int xx)
{
	if (k==0) return;
	if (num[k]<=xx) tmp1=k, Abefore(tree[k][1],xx);
	else Abefore(tree[k][0],xx);
}
int main()
{
	scanf("%d",&n);
	int x,y;
	for (int i=1;i<=n;++i)
	{
		scanf("%d%d",&x,&y);
		if (!root) kind=x, Insert(root,y,0);
		else if (kind==x) Insert(root,y,0);
		else
		{
			tmp1=tmp2=-1;
			Abefore(root,y), Aafter(root,y);
			if (tmp1==-1) ans+=num[tmp2]-y, ans%=mod, Del(tmp2);
			else if (tmp2==-1) ans+=y-num[tmp1], ans%=mod, Del(tmp1);
			else
				if (y-num[tmp1]>num[tmp2]-y) ans=(ans+num[tmp2]-y)%mod, Del(tmp2);
				else ans=(ans+y-num[tmp1])%mod, Del(tmp1);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

BZOJ-1507

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define NN 2010
using namespace std;

int n,m,a[NN][NN],f[NN][NN],l[NN][NN],r[NN][NN],h[NN][NN];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
	int ans1=1;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
		{
			if (i==1 || j==1) f[i][j]=1;
			else if (a[i][j]==a[i-1][j] || a[i][j]==a[i][j-1]) f[i][j]=1;
			else f[i][j]=min(f[i-1][j-1],min(f[i][j-1],f[i-1][j]))+1;
			ans1=max(ans1,f[i][j]);
		}
	printf("%d\n",ans1*ans1);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
		{
			if (i==1) h[i][j]=1;
			else if (a[i][j]==a[i-1][j]) h[i][j]=1;
			else h[i][j]=h[i-1][j]+1;
		}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
		{
			if (j==1) l[i][j]=j;
			else if (a[i][j]==a[i][j-1]) l[i][j]=j;
			else if (h[i][j-1]<h[i][j]) l[i][j]=j;
			else
			{
				l[i][j]=l[i][j-1];
				while (l[i][j]>1 && h[i][l[i][j]-1]>=h[i][j] && a[i][l[i][j]]!=a[i][l[i][j]-1])
					l[i][j]=l[i][l[i][j]-1];
			}
		}
	for (int i=1;i<=n;++i)
		for (int j=m;j>=1;--j)
		{
			if (j==m) r[i][j]=j;
			else if (a[i][j]==a[i][j+1]) r[i][j]=j;
			else if (h[i][j+1]<h[i][j]) r[i][j]=j;
			else
			{
				r[i][j]=r[i][j+1];
				while (r[i][j]<m && h[i][r[i][j]+1]>=h[i][j] && a[i][r[i][j]]!=a[i][r[i][j]+1])
					r[i][j]=r[i][r[i][j]+1];
			}
		}
	int ans2=0;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			ans2=max(ans2,h[i][j]*(r[i][j]-l[i][j]+1));
	printf("%d\n",ans2);
	return 0;
}

BZOJ-1861

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define NN 80050
#define LL long long 
#define INF 0x3f3f3f3f
using namespace std;

int n,m,size[NN],fa[NN],tr[NN][2],pos[NN],a[NN],v[NN],root=0;
void update(int k)
{
	size[k]=size[tr[k][0]]+size[tr[k][1]]+1;
}

void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l=(tr[y][0]!=x),r=l^1;
	if (y==k) k=x; 
	else if (tr[z][0]==y) tr[z][0]=x; else tr[z][1]=x;
	fa[x]=z, fa[y]=x, fa[tr[x][r]]=y;
	tr[y][l]=tr[x][r], tr[x][r]=y;
	update(y), update(x);
}
void Splay(int x,int &k)
{
	while (x!=k)
	{
		int y=fa[x],z=fa[y];
		if (y!=k)
		{
			if ((tr[y][0]==x)^(tr[z][0]==y)) rotate(x,k); else rotate(y,k);
		}
		rotate(x,k);
	}
}
void Build(int l,int r,int la)
{
	if (l>r)  return;
	int now=l, last=la;
	if (l==r)
	{
		v[now]=a[l], size[now]=1, fa[now]=last;
		if (l<la) tr[last][0]=now; else tr[last][1]=now;
		return;
	}
	int mid=(l+r)>>1; now=mid;
	Build(l,mid-1,mid), Build(mid+1,r,mid);
	v[now]=a[mid], fa[now]=last, update(now);
	if (mid<la) tr[last][0]=now; else tr[last][1]=now;
}
int Find(int k,int rank)
{
	int l=tr[k][0], r=tr[k][1];
	if (size[l]+1==rank) return k;
	else if (size[l]>=rank) return Find(l,rank);
	else return Find(r,rank-size[l]-1);
}
void Del(int k)
{
	int x=Find(root,k-1),y=Find(root,k+1),z;
	Splay(x,root), Splay(y,tr[x][1]);
	z=tr[y][0], tr[y][0]=0, fa[z]=size[z]=0;
	update(y), update(x);
}
void move(int k,int v)
{
	int x,y,z=pos[k],rank;
	Splay(z,root); rank=size[tr[z][0]]+1;
	Del(rank);
	if (v==INF) x=Find(root,n), y=Find(root,n+1);
	else if (v==-INF) x=Find(root,1), y=Find(root,2);
	else x=Find(root,rank+v-1), y=Find(root,rank+v);
	Splay(x,root), Splay(y,tr[x][1]);
	size[z]=1, fa[z]=y, tr[y][0]=z;
	update(y), update(x);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=2;i<=n+1;++i) scanf("%d",&a[i]),pos[a[i]]=i;
	Build(1,n+2,0);
	root=(n+3)>>1;
	char ch[10]; int x,y;
	for (int i=1;i<=m;++i)
	{
		scanf("%s",ch); scanf("%d",&x);
		if (ch[0]=='T') move(x,-INF);
		else if (ch[0]=='B') move(x,INF);
		else if (ch[0]=='I') scanf("%d",&y), move(x,y);
		else if (ch[0]=='A') Splay(pos[x],root), printf("%d\n",size[tr[pos[x]][0]]-1);
		else if (ch[0]=='Q') printf("%d\n",v[Find(root,x+1)]);
	}
	return 0;
}

BZOJ-1269

发现rope方法的长度和Splay的长度真是天壤之别

于是就开始学习偷懒技巧QAQ

//Rope
#include <cstdio>
#include <iostream>
#include <ext/rope>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
using namespace __gnu_cxx;

inline int read()
{
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}

#define NN 2000010

int n,now,len,x;
rope <char> a,b,tmp;
char ch[NN],chh[NN];

int main()
{
	n = read();
	while (n--)
	{
		scanf("%s",ch);
		switch (ch[0])
		{
			case 'M': now = read(); break;
			case 'P': now --; break;
			case 'N': now ++; break;
			case 'G': printf("%c\n",a[now]); break;
			case 'I':
				x = read(), len = a.length();
				for (int i=0;i<x;++i)
				{
					ch[i] = getchar();
					while (ch[i] == '\n') ch[i] = getchar();
					chh[x-i-1] = ch[i];
				}
				chh[x] = ch[x] = 0;
				a.insert(now,ch);
				b.insert(len-now,chh);
				break;
			case 'D':
				x = read(), len = a.length();
				a.erase(now,x);
				b.erase(len-now-x,x);
				break;
			case 'R':
				x = read(), len = a.length();
				tmp = a.substr(now,x);
				a = a.substr(0,now) + b.substr(len-now-x,x) + a.substr(now+x,len-now-x);
				b = b.substr(0,len-now-x) + tmp + b.substr(len-now,now);
				break;
		}
	}
	return 0;
}

BZOJ-1058

STL大法好啊QAQ

披着Splay外衣的STL

恩，窝还是把塔扔进了这里QAQ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
#define NN 500005

char ch[20];
int n,m,st[NN],ed[NN],p,x,tmp;
map <int,int> mp;
priority_queue <int, vector<int>,greater<int> > que;
multiset <int> a,b;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline void P(int xx)
{
	int l=*--b.lower_bound(xx), r = *b.lower_bound(xx);
	que.push(min(xx -l, r -xx));
	b.insert(xx);
}

inline void Ins(int xx)
{
	mp[xx] ++;
	if (mp[xx] == 1) a.insert(xx);
}

int main()
{
	n = read(), m = read();
	b.insert(INF), b.insert(-INF);
	for (int i=1;i<=n;++i)
	{
		x = read();
		st[i] = ed[i] = x;
		P(x);
	}
	for (int i=2;i<=n;++i) Ins(abs(st[i] - st[i-1]));
	while (m--)
	{
		scanf("%s",ch);
		if (ch[0] == 'I')
		{
			p = read(), x = read();
			if (p != n)
			{
				tmp = abs(ed[p] - st[p+1]);
				mp[tmp] --;
				if (!mp[tmp]) a.erase(tmp);
			}
			Ins(abs(ed[p] - x));
			Ins(abs(x - st[p+1]));
			ed[p] = x;
			P(x);
		}
		else if (ch[4] == 'S') printf("%d\n",que.top());
		else printf("%d\n",*a.begin());
	}
	return 0;
}

BZOJ-1503

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define NN 100010
#define INF 0x3f3f3f3f
using namespace std;

int sum[NN],tr[NN][2],fa[NN],num[NN],n,minn,root,size,delta=0,le=0;

inline void update(int k) {sum[k]=sum[tr[k][0]]+sum[tr[k][1]]+1;}
inline void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l=(tr[y][0]!=x),r=l^1;
	if (y==k) k=x;
	else if (tr[z][0]==y) tr[z][0]=x; else tr[z][1]=x;
	fa[x]=z, fa[y]=x, fa[tr[x][r]]=y;
	tr[y][l]=tr[x][r], tr[x][r]=y;
	update(y), update(x);
}
inline void Splay(int x,int &k)
{
	int y,z;
	while (x!=k)
	{
		y=fa[x], z=fa[y];
		if (y!=k)
			if ((tr[y][0]==x)^(tr[z][0]==y)) rotate(x,k); else rotate(y,k);
		rotate(x,k);
	}
}
inline int Dec(int &k,int xx)
{
	if (!k) return 0;
	int x;
	if (num[k]+delta<minn)
	{
		x=Dec(tr[k][1],k)+sum[tr[k][0]]+1;
		sum[tr[k][1]]=sum[k]-x;
		k=tr[k][1], fa[k]=xx;
	}
	else x=Dec(tr[k][0],k), sum[k]-=x;
	return x;
}
inline int Find(int k,int rank)
{
	int l=tr[k][0], r=tr[k][1];
	if (rank<=sum[r]) return Find(r,rank);
	if (rank==sum[r]+1)  return k;
	return Find(l,rank-sum[r]-1);
}
inline void Insert(int &k,int xx,int la)
{
	if (k==0) {k=++size, num[k]=xx, fa[k]=la, sum[k]=1, Splay(k,root); return;}
	if (xx<num[k]) Insert(tr[k][0],xx,k); else Insert(tr[k][1],xx,k);
}
int main()
{
	scanf("%d%d",&n,&minn);
	char ch[10];
	int x;
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch); scanf("%d",&x);
		switch (ch[0])
		{
			case'I':if (x>=minn) Insert(root,x-delta,0); break;
			case'A':delta+=x; break;
			case'S':delta-=x; le+=Dec(root,0); break;
			case'F':printf("%d\n",x<=sum[root]?num[Find(root,x)]+delta:-1); break;
		}
	}
	printf("%d\n",le);
	return 0;
}