來自《算法競賽入門經典訓練指南》

1.Treap實作名次樹

1.簡單介紹

Treap是一棵擁有鍵值和優先級兩種權值的樹。對于鍵值而言，這棵樹是二叉排序樹。對于優先級而言，這棵樹是堆，即在這棵樹的任意子樹中，根的優先級是最大的。不難證明，如果每個結點的優先級事先給定且互不相等，整棵樹的形态也就唯一确定了，和元素的插入順序無關。在Treap的插入算法中，每個節點的優先級是随機确定的。是以各個操作的時間複雜度也是随機的。幸運的是，可以證明插入、删除和查找的期望時間複雜度均為O(nlogn)。

2.Treap結點的定義

struct Node
{
    Node *ch[2];//左右子樹
    int r;//優先級，數值越大，優先級越高
    int v;//值
    int s;//結點總數
    int cmp(int x) const{
        if(x==v) return -1;
        return x<v?0:1;
    }
};

3.旋轉

分為左旋和右旋

//d=0表示左旋，d=1表示右旋
void rotate(Node* &o,int d)
{
    Node* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o=k;
}

注意小技巧:因為d=0或者1，d^1定價于1-d，但計算速度更快。關于左旋或者右旋，可自行百度……

4.插入結點

插入結點時，先随機給新結點一個優先級，然後執行普通的插入算法(根據鍵值大小判斷插入哪顆子樹中。執行完畢後，用左右旋，維護Treap樹的堆性質。如要采用遞歸實作，則隻需在遞歸插入之後判斷是否需要旋轉。

//在以o為根的子樹中插入鍵值x，修改o
void insert(Node* &o,int x)
{
    if(o==NULL){
        o=new Node();
        o->ch[0]=o->ch[1]=NULL;
        o->v=x;
        o->r=rand();
    }
    else{
        int d=o->cmp(x);
        insert(o->ch[d],x);
        if(o->ch[d]->r>o->r){
            rotate(o,d^1);
        }
    }
}

5.删除結點

删除結點，如果隻有一顆子樹，直接用這棵子樹代替待删除結點成為根即可(注意o是葉子的情況也符合在内)。麻煩的是o有兩棵子樹的情況，我們先把優先級較高的一顆旋轉到根，然後遞歸在另一棵子樹中删除結點o。例如，左子結點的優先級較高，就必須進行右旋，否則會違反堆性質。

void remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1){
        if(o->ch[0]==NULL) o=o->ch[1];
        else if(o->ch[1]==NULL) o=o->ch[0];
        else{
            int d2=(o->ch[0]->r>o->ch[1]->r?1:0);
            rotate(o,d2);
            remove(o->ch[d2],x);
        }
    }
    else{
        remove(o->ch[d],x);
    }
}

6.查找函數

上面的代碼沒有處理“待插入值存在”和“待删除值不存在”這兩種情況，是以在調用響應函數前，請進行一次查找。

int find(Node* o,int x)
{
    while(o!=NULL){
        int d=o->cmp(x);
        if(d==-1) return 1;//存在
        else o=o->ch[d];
    }
    return 0;//不存在
}

7.名次樹

在利用Treap實作名次樹中，每個結點均有一個附加域size，表示以它為根的子樹的結點的總數。名次樹可以實作如下兩種操作: Kth(k):找出第k小元素 Rank(x):值x的名次，即比x小的結點個數加1. 用Treap實作名次樹的方法是這樣的：新增一個size域，然後編寫一個maintain函數，方法如下:

void maintain()
{
    s=1;
    if(ch[0]!=NULL) s+=ch[0]->s;
    if(ch[1]!=NULL) s+=ch[1]->s;
}

旋轉操作也要修改，當s可能發生改變時，要調用maintain函數重新計算

//d=0表示左旋，d=1表示右旋
void rotate(Node* &o,int d)
{
    Node* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    //注意先維護o，再維護k
    o->maintain();
    k->maintain();
    o=k;
}

具體的模闆，見下面一道例題。

2.LA5031

1.題目原文

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3032

有一張n個頂點m條邊的無向圖，每個結點有一個整數權值。任務是執行一系列操作，操作分三種。 1.D X:删除ID為X的邊，保證每條邊至多删一次 2.Q X k:計算與結點X連通的結點中(包括X本身)，第k大的權值，如果不存在，傳回0. 3.C X V:把結點X的權值改為V。操作序列結束的标志是E。

2.解題思路

本題隻需要設計離線算法，是以可以把操作順序反過來處理。先讀入所有操作，執行所有的操作D時，按照逆序把這些邊逐漸插入到圖中。用一棵名次樹維護一個連通分量中的點權。C操作對應修改操作，Q操作對應kth操作，而執行D操作，如果兩個端點在一個連通分量中，顯然無影響。否則，應該像并查集合并的操作那樣，“權值”較小的并到“權值”較大的根節點中，這裡的權值是結點數，這樣的政策是啟發式合并。采用啟發式合并，可以高效處理(想一下并查集)，對于任意結點來說，每當它被移動到新樹中時，該結點所在樹的大小至少加倍，任意結點至多“被移動”logn次，每次移動需要O(logn)時間，是以總時間複雜度為O(nlog^2n)。

3.AC代碼

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include<cmath>
#include<bitset>
#include<sstream>
using namespace std;
#define INF 0x7fffffff

struct Node
{
    Node *ch[2];//左右子樹
    int r;//随機優先級
    int v;//值
    int s;//結點總數
    Node(int v):v(v){
        ch[0]=ch[1]=NULL;
        r=rand();
        s=1;
    }

    int cmp(int x) const{
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain(){
        s=1;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
};

//d=0代表左旋，d=1代表右旋
void rotate(Node* &o,int d)
{
    Node *k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o->maintain();
    k->maintain();
    o=k;
}

void insert(Node* &o,int x)
{
    if(o==NULL) o=new Node(x);else{
        int d=(x<o->v?0:1);//不要用cmp函數，可能有相同結點
        insert(o->ch[d],x);
        if(o->ch[d]->r>o->r) rotate(o,d^1);
    }
    o->maintain();
}

void remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1){
        Node *u=o;
        if(o->ch[0]!=NULL&&o->ch[1]!=NULL){
            int d2=(o->ch[0]->r > o->ch[1]->r?1:0);
            rotate(o,d2);
            remove(o->ch[d2],x);
        }
        else{
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
            delete u;
        }
    }
    else{
        remove(o->ch[d],x);
    }
    if(o!=NULL) o->maintain();

}

const int maxc=500000+10;
struct Command
{
    char type;
    int x,p;//根據type，p代表k或者v
}command[maxc];

const int maxn=20000+10;
const int maxm=60000+10;

int n,m;
int weight[maxn];
int from[maxm],to[maxm],removed[maxm];

//并查集相關
int pa[maxn];
int findset(int x)
{
    return pa[x]!=x?pa[x]=findset(pa[x]):x;
}

//名次樹相關
Node *root[maxn];

//第k大值
int kth(Node* o,int k)
{
    if(o==NULL||k<=0||k>o->s) return 0;
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(k==s+1) return o->v;
    else if(k<=s) return kth(o->ch[1],k);
    else return kth(o->ch[0],k-s-1);
}


void mergeto(Node* &src,Node* &dest)
{
    if(src->ch[0]!=NULL) mergeto(src->ch[0],dest);
    if(src->ch[1]!=NULL) mergeto(src->ch[1],dest);
    insert(dest,src->v);
    delete src;
    src=NULL;
}

void removetree(Node* &x)
{
    if(x->ch[0]!=NULL) removetree(x->ch[0]);
    if(x->ch[1]!=NULL) removetree(x->ch[1]);
    delete x;
    x=NULL;
}

//主程式相關
void add_edge(int x)
{
    int u=findset(from[x]),v=findset(to[x]);
    if(u!=v){
        if(root[u]->s<root[v]->s){
            pa[u]=v;
            mergeto(root[u],root[v]);
        }
        else{
            pa[v]=u;
            mergeto(root[v],root[u]);
        }
    }
}

int query_cnt;
long long query_tot;

void query(int x,int k)
{
    query_cnt++;
    query_tot+=kth(root[findset(x)],k);
}

void change_weight(int x,int v)
{
    int u=findset(x);
    remove(root[u],weight[x]);
    insert(root[u],v);
    weight[x]=v;
}

int main()
{
    int kase=0;
    while(scanf("%d%d",&n,&m)==2&&n){
        for(int i=1;i<=n;i++) scanf("%d",&weight[i]);
        for(int i=1;i<=m;i++) scanf("%d%d",&from[i],&to[i]);
        memset(removed,0,sizeof(removed));

        //讀指令
        int c=0;
        for(;;){
            char type;
            int x,p=0,v=0;
            scanf(" %c",&type);
            if(type=='E') break;
            scanf("%d",&x);
            if(type=='D') removed[x]=1;
            if(type=='Q') scanf("%d",&p);
            if(type=='C'){
                scanf("%d",&v);
                p=weight[x];
                weight[x]=v;
            }
            command[c++]=(Command){type,x,p};
        }

        //最終的圖
        for(int i=1;i<=n;i++){
            pa[i]=i;
            if(root[i]!=NULL) removetree(root[i]);
            root[i]=new Node(weight[i]);
        }

        for(int i=1;i<=m;i++){
            if(!removed[i]) add_edge(i);
        }

        //反向操作
        query_cnt=query_tot=0;
        for(int i=c-1;i>=0;i--){
            if(command[i].type=='D') add_edge(command[i].x);
            if(command[i].type=='C') change_weight(command[i].x,command[i].p);
            if(command[i].type=='Q') query(command[i].x,command[i].p);
        }

        printf("Case %d: %.6lf\n",++kase,query_tot/(double)query_cnt);
    }
    return 0;
}

用Treap實作名次樹1.Treap實作名次樹2.LA5031

1.Treap實作名次樹

1.簡單介紹

2.Treap結點的定義

3.旋轉

4.插入結點

5.删除結點

6.查找函數

7.名次樹

2.LA5031

1.題目原文

2.解題思路

3.AC代碼

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希