堆：stl裏有，make_heap等
歸並樹：
//
#include <algorithm>
using namespace std;
#define MN (100005)
struct node
{
int l,r;
}seg[4*MN];
int n;
int data[26][MN];
//數據放在data[0][1..n]中
void build(int l, int r, int dex, int level)
{
seg[dex].l=l;
seg[dex].r=r;
if(l==r){
data[level][l]=data[0][l];
return;
}
int mid = ( l + r ) / 2 ;
build( l , mid , dex * 2 ,level + 1);
build( mid+1 , r , dex * 2 + 1 , level + 1) ;
int i = l ,j = mid+1, k = l;
while( i <= mid && j <= r )
{
if(data[level+1][i] <= data[level+1][j])//排序的定義
data[level][k++] = data[level+1][i++];
else//可以找出逆序cnt+=mid-i+1;
data[level][k++] = data[level+1][j++];
}
while(i <= mid)data[level][k++] = data[level+1][i++];
while(j <= r)data[level][k++] = data[level+1][j++];
}
//query(1,c,l,r,1)，
int query(int root, int c, int l, int r, int dep)//(log n)^2
{
int mid=(seg[root].l+seg[root].r)/2;
if(l==seg[root].l && r==seg[root].r)
{
int * p=lower_bound(&data[dep][l],&data[dep][r]+1,c);
return (p-&data[dep][l]);//返回在區間段[l,r]中小於c的數的個數
//int *p=upper_bound(&data[dep][l],&data[dep][r]+1,c);
//return &data[dep][r]+1-p;//返回在區間段[l,r]中大於c的數的個數
}
if(r<=mid||l>=mid+1)return query(root*2+(l>=mid+1?1:0),c,l,r,dep+1);
else return query(root*2,c,l,mid,dep+1)+query(root*2+1,c,mid+1,r,dep+1);
}
////pku 2104
//
左偏樹：
//
#include <iostream>
using namespace std;
typedef int Elem;
struct Leftnode
{
Elem e;
int dist;
Leftnode * lson,* rson;
Leftnode(Elem ee){dist=0;e=ee;lson=rson=NULL;}
};//指針作為根，空樹root==NULL
Leftnode * Merge(Leftnode * A,Leftnode * B)
{//返回後*A，*B都沒有用了，但不空
if(A==NULL)return B;
if(B==NULL)return A;
if(A->e>B->e)swap(A,B);//最小堆
A->rson=Merge(A->rson,B);
if(A->lson==NULL||A->lson->dist<A->rson->dist)swap(A->lson,A->rson);
if(A->rson==NULL)A->dist=-1+1;//dis NULL:-1
else A->dist=A->rson->dist+1;
return A;
}
void insert(Elem ee,Leftnode * & root)//註意指針引用
{
Leftnode *tp=new Leftnode(ee);
root=Merge(root,tp);
}
bool delmin(Elem & ee,Leftnode * & root)//註意指針引用
{
if(root==NULL)return false;
ee=root->e;
root=Merge(root->lson,root->rson);
return true;
}
//hdu 1512