数据结构补充




2018/2/13,头有点晕emmmm…所以学一波数据结构,暂缓数论剩下的高深理论…

注意,这波数据结构是为了补充以前所不足的而撰写的,并无重头再来的意思.

并查集

要领

以前使用并查集多用于Kruskal的优化,现在要拓宽一下了.

并查集是不可能分割的,即只能合并,不可分割.

在牛客上听大佬讲课貌似存在可分割并查集,带权并查集.

现在拓宽下,并查集常用于判断加入一个点后是否会在原图上形成环.

或者判断有几个连通分量(通常是无向图),然后问你这些节点全部关联起来至少需要添加几条边.

实现前奏

首先是逻辑,并查集实现规则是一个点一个点入图时进行合并,即join,然后在合并时进行find,查找根节点是否相同,不同则将浅的树合并到深的树上,判断深浅通过每次合并时对rank进行操作,然后在一个优化是路径压缩,即如果a节点的最高根节点是c,则直接将a记录为c即可.

以上实现的前提是我们只需要逻辑上正确即可.

以题为马

HDU 1232
判断有多少个连通块,然后答案就是ans-1

#include<bits/stdc++.h>

using namespace std;

struct DisjointSet{
    vector<int> father,rank;
    int Num;
    DisjointSet(int n):father(n),rank(n),Num(n){
        for(int i=1;i<n;++i){
            father[i]=i;
        }
    }

    int find(int v){
        return father[v]=father[v]==v?v:find(father[v]);
    }

    void merge(int x,int y){
        int a=find(x),b=find(y);
        if(rank[a]<rank[b]){
            father[a]=b;
        }else{
            father[b]=a;
            if(rank[a]==rank[b]){
                ++rank[a];
            }
        }
    }

    int getCnum(){
        int ans=0;
        for(int i=1;i<Num;++i){
            if(father[i]==i) ans++;
        }
        return ans-1;
    }
};

int main(){
    int m,n;

    while(scanf("%d",&n) && n){
        DisjointSet ds(n+1);
        int s,t;
        scanf("%d",&m);
        for(int i=0;i<m;++i){
            scanf("%d %d",&s,&t);
            ds.merge(s,t);
        }
        printf("%d\n",ds.getCnum());
    }
    return 0;
}

单调栈

线段树区间更新和查询

POJ 3468

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000*4;
typedef long long LL;
int N,Q;
LL lazy[maxn];
LL sum[maxn];
LL tree[maxn];
LL a[maxn];

void build(int p,int l,int r){
    if(l==r){tree[p]=a[l];return;}
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}

void PushDown(int p,int m){
    if(lazy[p]){
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        sum[p<<1]+=(m-(m>>1))*lazy[p];
        sum[p<<1|1]+=(m>>1)*lazy[p];
        lazy[p]=0;
    }
}

void update(int p,int l,int r,int c,int L,int R){
    if(L<=l && r<=R){
        lazy[p]+=c;
        sum[p]+=(LL)(r-l+1)*c;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,c,L,R);
    if(R>mid) update(p<<1|1,mid+1,r,c,L,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

LL Query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return sum[p];
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=Query(p<<1,l,mid,L,R);
    if(R>mid) ret+=Query(p<<1|1,mid+1,r,L,R);
    return ret;
}

LL find(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return tree[p];
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=find(p<<1,l,mid,L,R);
    if(R>mid) ret+=find(p<<1|1,mid+1,r,L,R);
    return ret;
}

int main(){
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;++i) scanf("%lld",&a[i]);
    build(1,1,N);
    char op;
    int l,r,c;
    while(Q--){
        cin>>op;
        if(op=='Q'){
            scanf("%d%d",&l,&r);
            printf("%lld\n",Query(1,1,N,l,r)+find(1,1,N,l,r));
        }else if(op=='C'){
            scanf("%d%d%d",&l,&r,&c);
            update(1,1,N,c,l,r);
        }
    }
    return 0;
}