NOIp 数据结构专题总结 (1)：STL、堆、并查集、ST表、Hash表

系列索引：

NOIp 数据结构专题总结 (1)

NOIp 数据结构专题总结 (2)

STL structure

STL 在 OI 中的运用：https://oi.men.ci/stl-in-oi/

`std::vector`

#include <vector>

std::vector<type> v;

v.push_back(x);

v.pop_back();

int *a = new int[N];

`std::bitset`

#include <bitset>

std::bitset<size> bs;

神似 bool 数组。

SAO操作：

std::bitset<N> g[N]; // store a graph, O(n^2/32)

`std::map`

#include <map>

std::map<typeA, typeB> mp;

mp[x] = y;

map<int,bool> g[n];

g[x][y] = true;

map<int,bool>::iterator it;

for (it=g[x].begin(); it!=g[x].end(); ++it)

     it->first, it->second

`std::queue`

#include <queue>

std::queue<type> q;

q.push(x);

q.pop();

x = q.front();

`std::stack`

#include <stack>

std::stack<type> s;

s.push(x);

s.pop();

x = s.top();

`std::deque`

#include <queue> / #include <deque>

std::deque<type> dq;

`std::priority_queue`

#include <queue>

std::priority_queue<type> pq; // default: greater first

std::priority_queue<int, std::vector<int>, std::greater<int> > pq; // lower first

struct type { friend bool operator < (type a, type b) {return ...;} };

struct cmp { bool operator() (type a, type b) {return ...;} };

std::priority_queue<type, std::vector<type>, cmp> pq;

`std::set`

#include <set>

std::set<type> st;			// 会自动去重

std::multiset<type> st2; 	// 不去重

时间复杂度每次操作 \(O(\log{n})\)。

堆 Heap

Pure

复杂度均摊 \(O(\log{n})\).

void put(int x) {

    int now = ++heap_size, next;

    heap[heap_size] = x;

    while (now > 1) {

        next = now >> 1;

        if (heap[now] >= heap[next]) break; // lower root

        swap(heap[now], heap[next]);

        now = next;

    }

}

int get(int x) {

    int now = 1, next, res = heap[1];

    heap[1] = heap[heap_size--];

    while ((now << 1) <= heap_size) {

        next = now << 1;

        if (next < heap_size && heap[next+1] < heap[next]) next++;

        swap(heap[now], heap[next]);

    }

    return res;

}

堆的初始化：新建一个空堆，把这些元素依次加进堆，时间 \(O(n\log{n})\)。如果把这些元素 random_shuffle 一下再加进来，期望时间 \(O(n)\)。可以先随意把这些元素放进完全二叉树，再考虑从底向上令每个子树满足堆性质。

堆的删除：因为我们只关心堆顶的元素，我们可以把被删掉的元素暂时留在堆中，并保证当前堆顶的元素未被删除即可。一种实现方法是再开一个堆存储被删除但留在原堆中的元素，一旦两个堆堆顶相等，就一起弹出堆顶。总时间复杂度 \(

巴特西