常州集训Day7

今天早上学了堆&优先队列

//小根堆
    void push(int m){
    int i=l++;
    heap[i]=m;
    while(i>>1>0&&heap[i]>1]){
        swap(heap[i],heap[i>>1]);
        i=i>>1;
    }
}
void pop(){
    l--;
    heap[1]=MAX;
    swap(heap[1],heap[l]);
    int i=1;
    while(heap[i]>min(heap[i<<1],heap[(i<<1)+1])){
        if(heap[i<<1]<=heap[(i<<1)+1]){
            swap(heap[i],heap[i<<1]);
            i=i<<1;
        }
        else{
            swap(heap[i],heap[(i<<1)+1]);
            i=(i<<1)+1;
        }
    }
}

大家以前都学过就不详讲了

下午讲了并查集

int find(int x){//找根
    if(x==a[x])return x;
    a[x]=find(a[x]);//回溯时顺带标记，直接连接根节点，提高效率
    return a[x];
}
void s(int u,int v){//加边
    u=find(u);
    v=find(v);
    if(u!=v)a[u]=v;//合并两树
}

代码简单，但很高效