STL-set&multiset
以前不太会用，现在觉得挺好。（不过我不知道能不能用这个查元素排名，还有讲真常数挺大的 eg. bzoj3685会TLE）
二者都是用来维护数据结构的，插入的元素会排好序，每一次操作的复杂度都是log的
基本的函数啥的就不提了，度娘啥都有。
注意的几点：
1.set：元素不可重。multiset：元素可重
2.有一个神一样的函数s.count(x)返回一个int，表示集合中有多少个x，如果是set的话，只会返回1||0，表示有无元素，然而这tm是O(n)的。并不建议运用
3.lower_bound(x)返回iterator。指向优先级>=x的最前面的元素，如果没有，返回s.end( )
4.upper_bound(x)返回iterator。指向优先级>x的最前面的元素，如果没有，返回s.end( )
[写代码的时候一定要注意，呜呜呜，水题bz1208狂WA]
5.s.begin()指向s中第一个元素，s.end()指向最后面那个元素的后面，也就是s集合为[begin，end)，两个都一样。
6.迭代器只提供++或是--，但不能超范围。
7.s.erase(s,t)，删除集合中[s,t)中的元素。其中，s,t为iterator。如果想删元素需要把上面的lower_bound()和upper_bound()连用，注意删除区间是指针的左闭右开。两个都适用
8.s.clear()清空集合
9.s.erase(x)，可以是删除x这个元素，如果x是指针的话就是删除这个指针指向的元素。注意，如果s是multiset的话，会把所有的x元素都删除。
10.s.find(x)，返回一个指向元素x的迭代器，如果没有，返回end()。
另外发现了一个很好的blog，描述STL的函数很全面：【戳这里】
非旋转treap 好记好用
我曾经跨过山和大海，也穿过人山人海。也没有发现什么数据结构听一遍就直接会用。splay，treap，树状数组。。。理解+运用都需要好长一段时间。直到CKH发现了一个新的领域：非旋转treap！！！
同样为了使复杂度正确，非旋转treap给每个节点附上一个新的权值key。然后在合并的时候，维护一个堆(下文为大根堆)。同样也是中序遍历。
只有两个神操作；
1.merge(x,y) 将x,y为根的树合并
由于要维护堆，所以比较key[x],key[y]。将较大的当作新的根。然后合并大根的一个子树与另一棵树，递归。注意，x+y的中序遍历不变，也就是x，y合并的正确性建立在x+y的中序遍历的正确性上。
2.split(x,y)将以x为根的树在中序遍历的前y个与后面分开
返回一个pair，为新的两颗树的根。然后判断各种情况递归进行。
各种操作均可以用这两个操作实现，什么打lazy，插入，删除......
不过每次操作后的树都应为一颗以root为根的树，注意，是一颗。
下面附上普通平衡树的非旋转treap代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define mp(x,y) make_pair(x,y)
using namespace std;
typedef pair<int,int> pr;
int root,n,tot,op;
int ls[N],rs[N],w[N],siz[N],key[N];
void updata(int pos)
{
siz[pos]=siz[ls[pos]]+siz[rs[pos]]+1;
}
pr split(int x,int y)
{
if(y==0) return mp(0,x);
if(y==siz[ls[x]])
{
int t=ls[x]; ls[x]=0;
updata(x);
return mp(t,x);
}
if(y==siz[ls[x]]+1)
{
int t=rs[x];
rs[x]=0; updata(x);
return mp(x,t);
}
if(y<siz[ls[x]])
{
pr t=split(ls[x],y);
ls[x]=t.second; updata(x);
return mp(t.first,x);
}
pr t=split(rs[x],y-siz[ls[x]]-1);
rs[x]=t.first; updata(x);
return mp(x,t.second);
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(key[x]<key[y])
{
rs[x]=merge(rs[x],y);
updata(x);
return x;
}
ls[y]=merge(x,ls[y]);
updata(y);
return y;
}
void insert(int x,int y)
{
if(!root)
{
w[++tot]=y; siz[tot]=1; key[tot]=rand()*rand();
root=tot;
return ;
}
int l=0;
while(x)
{
if(w[x]>=y) x=ls[x];
else l+=siz[ls[x]]+1,x=rs[x];
}
pr t=split(root,l);
w[++tot]=y; siz[tot]=1; key[tot]=rand()*rand();
t.first=merge(t.first,tot);
root=merge(t.first,t.second);
}
void del(int x,int y)
{
int l=0;
while(x)
{
if(w[x]>=y) x=ls[x];
else l+=siz[ls[x]]+1,x=rs[x];
}
pr t=split(root,l);
t.second=split(t.second,1).second;
root=merge(t.first,t.second);
}
void q_rank(int x,int y)
{
int ans=0;
while(x)
{
if(w[x]>=y) x=ls[x];
else ans+=siz[ls[x]]+1,x=rs[x];
}
printf("%d\n",ans+1);
}
void q_val(int x,int y)
{
while(x)
{
if(y<=siz[ls[x]]) x=ls[x];
else
{
y-=siz[ls[x]]+1;
if(!y){printf("%d\n",w[x]); return ;}
x=rs[x];
}
}
}
void q_before(int x,int y)
{
int l=0;
while(x)
{
if(w[x]>=y) x=ls[x];
else l=x,x=rs[x];
}
printf("%d\n",w[l]);
}
void q_after(int x,int y)
{
int r;
while(x)
{
if(w[x]<=y) x=rs[x];
else r=x,x=ls[x];
}
printf("%d\n",w[r]);
}
int main()
{
scanf("%d",&n);
int x;
while(n--)
{
scanf("%d%d",&op,&x);
switch(op)
{
case 1:insert(root,x); break;
case 2:del(root,x); break;
case 3:q_rank(root,x); break;
case 4:q_val(root,x); break;
case 5:q_before(root,x); break;
case 6:q_after(root,x); break;
}
}
return 0;
}
RMQ&&LCA
额，前置技能perfect!!!。
先认识一个叫做欧拉遍历序的东西，就是在dfs的过程中当第一次搜到一个点的时候记录这个点，当一个儿子搜完之后再记录这个点的序列。大概是这个意思：
void dfs(int x)
{
in[x]=++tot; rank[tot]=x; deep[x]=deep[fa[x]]+1;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
fa[to[i]]=x;
dfs(to[i]);
rank[++tot]=x;
}
}
我们发现这个序列每条边退出的时候起始点被记录了一次，每个点在dfs到的时候被记录了一次，所以共有2n-1个点。
发现这样一个性质，任意两个点入栈时间戳对应的闭区间中deep最小的点就是两点的lca。
那么我们只需要知道区间deep最小值所在的点就好了。我们可以进行RMQ操作，每次比较区间的ans哪一个deep最小，然后在查询的时候就可以O(1)出解啦。2333
具体写法：
1.求出欧拉遍历序：之前写了
2.预处理：
for(int i=2;i<=tot;i++) Log[i]=Log[i>>1]+1;
for(int i=1;i<=tot;i++) lca[i][0]=rank[i];
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=tot;j++)
lca[j][i]=deep[lca[j][i-1]] < deep[lca[min(j+(1<<i-1),tot)][i-1]]?lca[j][i-1]:lca[min(j+(1<<i-1),tot)][i-1];
3.O(1)查询：
if(in[x]>in[y]) swap(x,y);
tmp=Log[in[y]-in[x]+1];
anc=deep[lca[in[x]][tmp]]<deep[lca[in[y]-(1<<tmp)+1][tmp]]?lca[in[x]][tmp]:lca[in[y]-(1<<tmp)+1][tmp];
新技能get√。