我在wiki上发现了N种平衡树。。不得不感叹数据结构的博大精深。。
AVL和SBT实际上思想上差不多。。
都是运用某种数值将树平衡起来。。
AVL是高度。。SBT是大小。。
在AVL中两棵子树高度不会差太多（从而保证大小不差太多）。。
SBT中大小不会差太多。。
甚至我感觉SBT就是简化版的AVL。。
因为其中左孩子大小不小于右边的两个孙子大小的规定
太像高度不差一了。。

Treap比较NB。。它利用了随机树是平衡的
所以用了一种tree+heap的方法动态产生随机树。。
但树高度就不怎么样了。。
但他是最好写的。。

红黑树是用节点的颜色来是树中任意两条路径长度不差2倍。。
所以也是平衡的。。不过总是让我感觉太精巧和复杂了。。
不知是怎么想出来的。。算法导论上有。。就不多说了。。

2-3树更诡异。。它跟AA树是同构的。。
他一个节点可以是普通的2节点。。就是两个孩子。。
也可以是3节点。。就是说3个孩子。。
一般的节点存一个值。比如是x。。
将子树分为<x和>x的。。
而3节点存两个值x,y。。
将子树分为<x,(x,y),>y三个部分。。
然后在插入的时候如果2节点变成3节点了。。没事。。
如果3节点变4节点了。。就分裂一下。。把中间那个提上去。。。。
2-3树高度是严格logn的。。不过3节点很多。。
查起来也差不多是2logn的。。。

2-3-4树。。就是说不但有2，3节点。。还有4节点。。搞死人的东西。。
跟2-3树差不多。。

splay。。我最喜欢的。。它主要就是每次访问到一个节点。。就把它转成根。。
算是最NB和自然的数据结构了。。不过就是太慢了。。
个人感觉是最好写的。。这家伙的长度一般是3-4*logn。。

红黑树有一个很BT的特点就是维护的时候最多旋转2次。。。所以stl就用这个了。。
而AA树是红黑树的一个变种。。规定左边的孩子不能为红色。。所以维护的时候可能转的
更多。。但似乎是AA树更快一点。。不过stl追求的是稳定。。

Scapegoat tree是让两个孩子的大小都小于a*父亲的大小。。
维护起来很诡异。。每次都是找一个最高的那个不满足的顶点。。
直接暴力重建成近完全2叉树。。均摊是logn的。。

上次我使用splay。。没有A掉这道题。。非常的不爽。。
这次使用treap。。总算亲自把它A了。。
题目就看上一个吧。。基本的平衡树。。。
据说如果随机数据的话。。
AVL和SBT差不多是1*logn
Splay是3～4*logn的。。
Treap是2～3*logn的。。
实际上这道题离散化一下。。然后用线段树也能A。。估计快很多。。
Code:
http://ideone.com/Fie69wNz

再过5分钟就数学考试了..妈呀

     最近我买了一个touch。。。我经过多天的钻研。。将其成功变成了一个pda（掌上电脑）
比如说
有wifi可以用safari上网。。可以用stanza在线下小说看。。比如九鼎记之类的。。。可以拼命玩游戏。。。。。。还可以用fileapp装书进去看。。pdf啊word啊ppt啊网页啊txt啊chm啊都可以看。。。
还能打代码编程（这点最NB..）。。只要装个编译器就可以了。。。
不过马上就要中考了。。。我得复习去了。。。

给一棵树。。每个叶子节点有一个权值，对每一个非叶子节点求出其子树中两两对中最小的绝对值差。。
dfs一下。。可以用一个平衡树维护信息，合并就可以启发式插入，并维护最小绝对值差就可以了。。。
加个分析吧。。看上去暴力合并可能会很慢。。但实际上可以证明是很快的。。
你看一个点如果每被插入一次，它所在的树的大小至少*2。。那么它就最多被插入logn次，总共最多也就是nlogn。。实际上还没有nlogn次的。。可以证明插入的是n量级的。。
那么每次插入是logn的。。总算法也就是nlogn的了。。
Code：
ideone.com/3PjCARDF

就是说一个数的质因数只有2和3和5的数叫ugly数。。让你求第N个ugly数，N<=1500。。。
注意到第一个是1。。然后用一个最小堆维护当前ugly数集合。。每次取出最小的。并把它的2、3、5倍放入堆中就OK了。。注意要去重。。。
在家复习的累死。。做到编程题放松放松。。。
代码。。
ideone.com/HbO4lIIm

做了很多数据结构题。。以前找题目的时候老师翻遍OJ很痛苦。。以做个合集方便大家啦解法自然会有很多。。我就按我的做法分了。。代码有些我放在idone上了。。一个很好的网站。。代码很漂亮 。。。
几个月过去了。。我再次更新这篇文章。。。
树状数组：
[SDOI2009]HH的项链 用树状数组帮助离线算法的处理。。
平衡树：
Splay：
SPOJ GSS6：http://hi.baidu.com/wjbzbmr/blog/item/de1a10c9b3608cf653664fed.html
动态数列维护的问题
SPOJ QMAX3VN：hi.baidu.com/wjbzbmr/blog/item/de1a10c9b3608cf653664fed.html
动态数列维护
SPOJ ORDERSET：hi.baidu.com/wjbzbmr/blog/item/5574dbefee16b1dfb21cb150.html
基本平衡树操作。。splay太慢过不掉。。。
sgu 187：hi.baidu.com/wjbzbmr/blog/item/aadf04c8bbc59e8dc91768bf.html
动态维护反转。。。
Splay的代码：hi.baidu.com/wjbzbmr/blog/item/72dfd036fd160545251f148e.html
基本的splay。。。
Treap:
SPOJ ORDERSET hi.baidu.com/wjbzbmr/blog/item/5e083684dd53ee3566096e76.html
用Treap也A掉了。。但我自己写的SBT太慢。。没A掉。。
线段树：
POJ3667：hi.baidu.com/wjbzbmr/blog/item/26c1dd0abcc82a9e0b7b82f9.html
很经典的懒标记题目了。。
SPOJ GSS5：hi.baidu.com/wjbzbmr/blog/item/a7f4a5996fd888bfc8eaf4d5.html
普通最大连续和的扩展。。分别限定开始和结束位置
SPOJ GSS1、3：http://hi.baidu.com/wjbzbmr/blog/item/6690a428485cac325343c1aa.html
最经典的最大连续和。。
[Scoi2010]序列操作 复杂的线段树问题，降低Coding复杂度是重点。。。
经典的题目了。。
树：
POJ 1984-1987：http://hi.baidu.com/wjbzbmr/blog/item/3dd10211e494368a6438dbdc.html
1984：并查集
1985：一颗树中距离最远的两点，经典算法。。。
1986：树中两点的距离。。直接Tarjan。。
1987：基于边的分治。。很难饿。。
并查集：
堆，可合并堆：
POJ 1338:hi.baidu.com/wjbzbmr/blog/item/d11f1cb3d9af3e5f082302ee.html
比较有意思的堆题目（也可以不用堆吧。。暴力生成然后再排序应该也可以。。）
块状XX(链表，数组)：
Zju2112 Dynamic Rankings 区间K大值，要支持修改

Hash：
SPOJ ABCDEF：http://hi.baidu.com/wjbzbmr/blog/item/5aa21437dd53dd1a91ef3938.html
杂七杂八的：

大意：NOI维护数列的简化版。。
我什么时候把维护数列也A掉就爽了。。。
4个操作
1:insert(p,x) 在第p-1个数之后插入一个数x
2:delete(p) 删除第p个数
3:max(l,r) 输出l到r之间的最大连续和
4:replace(p,x) 将第p个数换成x。。
我写了两个程序。。一个块状数组，一个splay。。
块状数组妈妈的太慢了。。。
insert直接把第p-1个数转成根，第p个数转到根下面，那么直接把这个数放到第p个数的左子树就行了。。
delete把第p个数找到。。然后一直转到没有左儿子。。再删除它。。
max只要把第l-1个数转成根，第r+1个数转到根下面。。就OK了。。
replace跟insert基本一样。。。
转好了之后，别忘了splay哦！
还有Null的参数设置，也是需要考虑的。。。
splay太NB了。。。
俄。也不是，维护数列里面没要求删除的。。不过也差不多。。
12.4s。。。感觉原来发代码太占空间了。。放到ideone上面吧。。很漂亮。。
Code:http://ideone.com/aoAEParp

给一个大小于100的集合S
求满足下两式的六元组个数。。

d！＝0。。。
化一下，a*b+c=(e+f)*d。。
现用Hash把所有efd枚举一下，Hash存下结果。。
然后枚举abc就OK了。。
O(n^3)
这提示我一般的找个数的题目，如果适当Hash都可以降低复杂度。。。
Code:
#include<cstdio>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int size=100007;
class Hash
{
struct node
{
int x,s;
node*next;
}*H[size],Data[1000000],*Now;
node* new_node(int x,int s,node*n)
{
Now->x=x;Now->s=s;Now->next=n;
return Now++;
}
int Code(int x)
{
if(x<0)x=-x;
return x%size;
}
public:
Hash()
{
Now=Data;
memset(H,0,sizeof(H));
}
void ins(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
{p->s++;return;}
node*q=new_node(x,1,H[h]);
H[h]=q;
}
int find(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
return p->s;
return 0;
}
};
class solve
{
int n,A[100];
void init()
{
scanf("%d",&n);
REP(i,n)
scanf("%d",A+i);
}
void work()
{
Hash H;
REP(i,n)REP(j,n)REP(k,n)if(A[k])
H.ins((A[i]+A[j])*A[k]);
int ans=0;
REP(i,n)REP(j,n)REP(k,n)
ans+=H.find(A[i]*A[j]+A[k]);
printf("%dn",ans);
}
public:
solve()
{
init();
work();
}
};
int main()
{
solve now;
}

这道题是说。一列数，两个操作，
(1):insert(p,x)在第p-1个数后插入数x
(2):max(l,r)输出第l个数到第r个数中最大的数
直接上splay。。splay太厉害了。。
Code:ideone.com/WDlkwwnX