数据结构

Posted on Views:

单调栈

1
2
3
4
5
6
7
8
9
10
11
// 常见模型：找出每个数左/右边离它最近的比它大/小的数
// 以下代码是找到每个数左边第一个比它小的数
stack<int> stk;
for(int i = 0; i < n; i++)
{
    cin >> a;
    while(stk.size() && a <= stk.top()) stk.pop(); // 对于后面的数来说，a 比当前栈顶更优
    if(stk.size()) cout << stk.top() << " ";
    else cout << "-1 ";
    stk.push(a);
}

对顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template<typename T>
class Topheap
{
public:
    priority_queue<T> less;  //存放 <= mid 的数，大顶堆
    priority_queue<T, vector<T>, greater<T>> more; // 存放 > mid 的数，小顶堆
    // 中位数就是less中的top
    // less的size要保证 == more || == more + 1
    const T inf = 2e9;
    Topheap(){less.push(-inf), more.push(inf);}
    void adjust()
    {
        if(less.size() > more.size() + 1)
        {
            more.push(less.top());
            less.pop();
        }

        if(less.size() < more.size())
        {
            less.push(more.top());
            more.pop();
        }
    }
    void push(T x)
    {
        if(x <= less.top()) less.push(x);
        else more.push(x);
        adjust();
    }

    T get(){ return less.top();}
};

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class DSU
{
public:
    vector<int> p;
    // vector<int> sz; // 维护集合大小
    // vector<int> dis;// 维护到祖宗节点的距离
    Dsu(int n = 0){
        p.resize(n);
        // sz.resize(n, 1);
        // dis.resize(n, 0);
        for(int i = 0; i < n; i++) p[i] = i;
    }

    int find(int x)
    {
        if(p[x] != x)
        {
            int u = find(p[x]);
            // dis[x] += dis[p[x]]; // 要加上它的父节点到根节点的距离
            p[x] = u;   // 路径压缩
        }
        return p[x];
    }    

    void merge(int a, int b)
    {
        int ra = find(a), rb = find(b);
        if(ra != rb)
        {
            // size[rb] += size[ra];
            // dis[a] = distance[a, b];
            p[ra] = rb;
        }
    }
};

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template<typename T>
class Fenwick
{
public:
    vector<T> t;
    int n;
    Fenwick(int _n = 0){
        n = _n;
        t.resize(n + 1);
    }
    // 二进制数最后一个1
    int lowbit(int x){ return x & -x};

    void update(int x, T d)
    {
        while(x <= n)
        {
            t[x] += d;
            x += lowbit(x);
        }
    }

    T sum(int x)
    {
        T ans = 0;
        while(x > 0)
        {
            ans += t[x];
            x -= lowbit(x);
        }
        return ans;
    }
}