并查集

1250. 格子游戲

• 并查集解決的是連通性（無向圖聯通分量）和傳遞性（家譜關系）問題，并且可以動態的維護。拋開格子不看，任意一個圖中，增加一條邊形成環當且僅當這條邊連接的兩點已經聯通，于是可以將點分為若干個集合，每個集合對應圖中的一個連通塊。
• 并查集(典型并查集判斷是否存在環的問題)
• 并查集中一般用一維的坐標會方便一些，所以這個題要把二維坐標轉化成一維坐標，有個很常用的方式，(x,y) -> x*n+y，前提是x和y都從0開始
• 將每個坐標看成一個點值，為了方便計算，將所有的坐標橫縱坐標都減1，第一個位置即(1,1)看成是0，(1,2)看成是1，依次類推，將所有的坐標橫縱坐標都減1后，假設當前點是(x,y),則該點的映射值是a = (x * n + y)，若向下畫，則b = [(x + 1) * n + y],若向右畫，則b = [x * n + y - 1]
• 并查集操作復雜度接近O(1)，本來應該這題是O(n+m)，但由于實現時只用了路徑壓縮，沒有用什么什么合并，所以本質這道題復雜度是mlogn的，但這個logn非常小，因為并查集常數很小，

#include <iostream>using namespace std;const int N = 40010; // 200 * 200int n, m; int fa[N];int get(int x, int y) {return x * n + y; }int find(int x) {if (fa[x] != x) fa[x] = find(fa[x]);return fa[x]; }int main() {cin >> n >> m;// for (int i = 1; i <= n; i ++ ) fa[i] = i;for (int i = 0; i < n * n; i ++ ) fa[i] = i; // wa!!!! [0, n * n - 1]int res = 0;for (int i = 1; i <= m; i ++ ){int x, y;char d;cin >> x >> y >> d;x -- , y -- ;int a = get(x, y);int b;if (d == 'D') b = get(x + 1, y);else b = get(x, y + 1);int pa = find(a), pb = find(b);if (pa == pb){res = i;break;}fa[pa] = pb;}if (!res) cout << "draw" << endl;else cout << res << endl;return 0; }

樹狀數組

• 樹狀數組相較于數組和前綴和數組的作用

• 采取的是二進制思想，例如求1~x的和，就可以用下圖的方案在log(x)中算出；即可以在log(n）時間內算出前n項的前綴和
  
• 那如何求每個區間的和呢？先看看區間的性質，第一個區間包含$2^{i_1}$個數，第二個區間包含$2^{i_2}$個數，以此類推，然后發現$2^{i_1}$是x的二進制表示的最后一位1，$2^{i_2}$是x - $2^{i_1}$的最后一位1。因此，在這樣的(L, R]區間中，這個區間長度一定是R的二進制表示的最后一位1所對的次冪。（lowbit(x)是O(1)的），那么這個區間形式就可以改寫為[R-lowbit( R)+1,R]，那么就可以用數組，C[R]來表示這個區間的總和了，這樣的區間最多有n個。
• C[x] = a[x - lowbit( x) + 1, x]，對于每個x而言，1～x的所有數的和，最多可以拆成log(x)個C[x]的和，所以是log(n)
  
  
• 這樣就挖掘出了所有不同C之間的關系

241. 樓蘭圖騰

#include <iostream> #include <cstring>using namespace std;typedef long long ll;const int N = 2e5 + 10;int n; int a[N], tr[N]; int Greater[N], lower[N];int lowbit(int x) {return x & (-x); }void add(int x, int c) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; }int sum(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res; }int main() {scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);// 從左到右for (int i = 1; i <= n; i ++ ){int y = a[i];Greater[i] = sum(n) - sum(y); // [y + 1, n] // y + 1 ~ n之間已出現的數的個數lower[i] = sum(y - 1); // [1, y - 1] // 1 ~ y - 1之間已出現的數的個數add(y, 1); // 記錄y這個數已經出現了}memset(tr, 0, sizeof tr); // 清空，重新建樹，之間是從左向右遍歷數組建樹，后面要從右向左了ll res1 = 0, res2 = 0;for (int i = n; i; i -- ){int y = a[i];res1 += Greater[i] * (ll)(sum(n) - sum(y));res2 += lower[i] * (ll)(sum(y - 1));add(y, 1);}printf("%lld %lld", res1, res2);return 0; }

線段樹

// 簡單線段樹的操作 ：//傳入節點編號，用子節點信息來算父節點信息 push up（int u）//將一段區間初始化為一顆線段樹 build()//修改操作,修改某一個點或者某一個區間（懶標記） modify()//查詢某一段區間的信息 query()

• 定義 ：線段樹是一顆滿二叉樹，以一顆長度為10的序列為例 ：
  
• N個葉結點的滿二叉樹有N + N/2 + N/4 + … = 2N-1個結點，因為在上述存儲方式下，最后還有一層產生了空余，最后一層最壞情況下是上一層的兩倍，也就是還有2N個，所以保存線段樹的數組長度要不小于4N
• 線段樹的查詢操作，例如查詢【5， 9】，有8個區間要查 。且可以發現為log(n)，不過最多有4logn，而樹狀數組只有1logn，所以線段樹復雜度更大
  
• 線段樹的結構 ：

//一般使用結構體來存儲線段樹,空間大小開四倍 struct Node{int l,r; //維護的區間int v; //維護的信息... } tree[N*4];

• 線段樹的建樹 ：

//build void build(int u,int l,int r){ //構建節點u，其維護的是區間[l,r]tr[u]={l,r};if(l==r) return ; //已經是葉子節點int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r); }

• push_up操作 ：

//push_up操作,用子節點信息來更新父節點信息,以維護最大值為例 void push_up(int u){tree[u].v=max(tree[u<<1].v,tree[u<<1|1].v); }

• 查詢操作 ：

//query操作，用來查詢某一段區間內的信息,以最大值為例 int query(int u,int l,int r){ //從u節點開始查詢[l,r]區間內的某一信息if(tree[u].l>=l&&tree[u].r<=r) return tree[u].v; //說明這一段的信息已經被完全包含，因此不需要繼續向下遞歸，直接返回即可int res=0;//否則需要判斷該遞歸那一邊int mid=tree[u].l+tree[u].r >> 1;if(l<=mid) res=max(res,query(u<<1,l,r)); //遞歸左邊并更新信息if(mid<r) res=max(res,query(u<<1|1,l,r)); //遞歸右邊并更新信息,切記是mid<r，無等號return res; }

• 修改操作

//query操作，用來查詢某一段區間內的信息,以最大值為例 int query(int u,int l,int r){ //從u節點開始查詢[l,r]區間內的某一信息if(tree[u].l>=l&&tree[u].r<=r) return tree[u].v; //說明這一段的信息已經被完全包含，因此不需要繼續向下遞歸，直接返回即可int res=0;//否則需要判斷該遞歸那一邊int mid=tree[u].l+tree[u].r >> 1;if(l<=mid) res=max(res,query(u<<1,l,r)); //遞歸左邊并更新信息if(mid<r) res=max(res,query(u<<1|1,l,r)); //遞歸右邊并更新信息,切記是mid<r，無等號return res; }

1275. 最大數

• 這道題的兩個操作可以被轉化成上述兩個操作，而這兩個操作就是線段樹的經典操作，動態修改某個位置上的數，動態查詢某個區間內的最大值
• 不過，這個問題比較特殊，每個位置只會被修改一次，因此這題可以用RMQ算法做，可以看作靜態問題，不過局限性比較大，只能處理靜態數據。但其實不是如此，這題由于每次修改的時候依賴上一次查詢的，是動態的問題，不能把它全部讀進來然后預處理去做的，所以不能用RMQ
• 注意！！凡是只要修改某一個點，單點，的，都不需要用到懶標記，本身都可以做到Logn的復雜度；凡是涉及到區間的，修改整一個區間的，這樣的操作，一般都需要加上懶標記，否則復雜度會退化
• pushup由兒子算父節點的信息，pushdown是父節點的修改更新到兒子上面

#include <iostream>using namespace std;typedef long long ll;const int N = 2e5 + 10;int m, p; struct Node {int l, r;int v; // 區間[l, r]中的最大值 }tr[N * 4];void pushup(int u) // 由子結點的信息，來計算父節點的信息 {tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v); }void build(int u, int l, int r) {tr[u] = {l, r};if (l == r) return ; // 葉子結點int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); }int query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 樹中結點，已經被完全包含在[l, r]中了int mid = tr[u].l + tr[u].r >> 1;int v = 0;if (l <= mid) v = query(u << 1, l, r);if (r > mid) v = max(v, query(u << 1 | 1, l, r));return v; }void modify(int u, int x, int v) {if (tr[u].l == x && tr[u].r == x) tr[u].v = v; // 葉節點，遞歸出口else{int mid = tr[u].l + tr[u].r >> 1;if (x <= mid) modify(u << 1, x, v);else modify(u << 1 | 1, x, v);pushup(u); // 回溯，用子結點的信息更新父節點信息} }int main() {int n = 0, last = 0; // n表示樹中結點個數，last保存上一次查詢的結果scanf("%d%d", &m, &p);// 初始化線段樹，結點的區間最多為[1, m]build(1, 1, m);int x;char op[2]; // 可以讀空字符while (m -- ){scanf("%s%d", op, &x);if (*op == 'Q'){last = query(1, n - x + 1, n); // 查詢[n - x + 1, n]內的最大值，u = 1，即從根結點開始查詢printf("%d\n", last);}else{modify(1, n + 1, ((ll)last + x) % p); // 在n + 1處插入 // 需要將last + x的結果強制轉換成ll，否則可能會溢出n ++ ; // 結點個數 ++}}return 0; }

可持久化數據結構

• 可持久化的前提 ：這個數據結構本身的拓撲結構在操作過程中保持不變。
• 可持久化數據結構 ：1.trie的可持久化。2.線段樹的可持久化-主席樹。比如線段樹，只會變線段樹里面的信息，線段樹本身是不會發生變化的。樹狀數組每個結點的兒子也是固定不變的，變的只是里面存的信息。堆也是，結構不會發生變化，完全二叉樹；而有些數據結構會發生拓撲序的變化，比如平衡樹，左旋和右旋，操作后結點之間的拓撲序會發生變化。
• 可持久化解決的問題是什么 ：可以存下來數據結構的所有歷史版本
• 核心思想 ：只會記錄當前版本和前一個版本不一樣的地方。比如線段樹，每次修改，如果n個結點，操作涉及最多4logn個結點，每次操作最多改變的節點數只有o(logn)個。即，最多只會記錄mlogn個結點
• 可持久化trie ：
  

• 凡是有變化的點就裂開成一個新的點，比如根結點就每次必然有變化

256. 最大異或和

• 原始數據最多有3e5，再加上3e5個操作，因此整個序列長度最大是6e5
• 2^24正好大于10 ^7，所以trie長度最多為24，再加上根結點，所以每次最多建立25個新結點
  

#include <iostream>using namespace std;// 30w初始數據和30w新增, 而10的7次方小于2的24次方, 再加上根節點, 就是說每個數最多需要25位; const int N = 6e5, M = N * 25;int n, m; int s[N]; // 前綴和序列 int tr[M][2]; int max_id[M]; // 用于記錄當前根結點版本的最大id范圍 int root[N], idx;// i是第i個插入的數的i，k是現在取到第k位，p是上一個插入的數的結點號，q是當前節點號 void insert(int i, int k, int p, int q) {// 如果記錄結束了if (k < 0){max_id[q] = i; // 記錄當前節點(可能會被后面公用)所能到達的最大范圍ireturn ;}int v = s[i] >> k & 1;// 如果前一個節點存在當前節點沒有的分支, 那就把當前節點的這個空的路徑指過去, 這就相當于復制! v ^ 1指的是與v相反的一側if (p) tr[q][v ^ 1] = tr[p][v ^ 1];tr[q][v] = ++ idx; // 現在才是正常trie樹插入，給v開辟一個新結點insert(i, k - 1, tr[p][v], tr[q][v]); // 以v這個結點為父節點，繼續往下處理max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]); }int query(int root, int C, int L) // L為限制 即L ~ root之間的版本是符合要求的 {int p = root;for (int i = 23; i >= 0; i -- ){int v = C >> i & 1;if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];else p = tr[p][v];}return C ^ s[max_id[p]]; }int main() {scanf("%d%d", &n, &m);s[0] = 0;max_id[0] = -1;root[0] = ++ idx;insert(0, 23, 0, root[0]);for (int i = 1; i <= n; i ++ ){int x;scanf("%d", &x);s[i] = s[i - 1] ^ x;root[i] = ++ idx;insert(i, 23, root[i - 1], root[i]);}char op[2];int l, r, x;while (m -- ){scanf("%s", op);if (*op == 'A'){scanf("%d", &x);n ++ ;s[n] = s[n - 1] ^ x;root[n] = ++ idx;insert(n, 23, root[n - 1], root[n]);}else{scanf("%d%d%d", &l, &r, &x);// 至少要包住第r個點, 所以用r-1, 否則會因為異或把root[r]抵消掉// l也同理printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));}}return 0; }

平衡樹Treap

253. 普通平衡樹

AC自動機

1282. 搜索關鍵詞

總結

以上是生活随笔為你收集整理的AcWing算法提高课 Level-3 第四章 高级数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。