塊狀鏈表是一個(gè)集合了分塊和鏈表的優(yōu)秀數(shù)據(jù)結(jié)構(gòu)。鏈表的每一個(gè)指針指向一個(gè)數(shù)組，每個(gè)數(shù)組的大小都接近 \(\sqrt{n}\)，因此塊狀鏈表的復(fù)雜度都為 \(\sqrt{n}\)。

大概長(zhǎng)這樣。（圖片來自 \(\texttt{OI-Wiki}\)）

可以用它水過普通平衡樹例題，所以又稱為“五分鐘平衡樹”。

塊狀鏈表支持插入、分裂、查找等操作。

list<vector<ll>> List;

using lit = list<vector<ll>>::iterator;
using vit = vector<ll>::iterator;

基本操作

查找

遍歷鏈表，來找到被查找元素的位置。

lit find(const int &p) {
    int cnt = 0;
    for (lit it = List.begin(); it != List.end(); ++ it) {
        if ((*it).back() >= p) {
            return it;
        }
    }
}

（插入）分裂

當(dāng)一個(gè)數(shù)組的大小超過 \(2 \times \sqrt{n}\) 時(shí)，執(zhí)行分裂操作以保證復(fù)雜度，否則就會(huì)退化成普通數(shù)組。

具體應(yīng)該怎么做呢？在鏈表上新建一個(gè)節(jié)點(diǎn)和數(shù)組，將被分裂節(jié)點(diǎn)的后 \(\sqrt{n}\) 個(gè)值復(fù)制到新節(jié)點(diǎn)上，被分裂節(jié)點(diǎn)在刪除后 \(\sqrt{n}\) 個(gè)值。

void insert(int x) {
    lit it = find(x);
    (*it).emplace(lower_bound((*it).begin(), (*it).end(), x), x);
    if ((*it).size() > lim) {
        List.emplace(next(it), (*it).begin() + (lim / 2), (*it).end());
        (*it).erase((*it).begin() + (lim / 2), (*it).end());
    }
}

刪除

void erase(int x) {
    lit it = find(x);
    (*it).erase(lower_bound((*it).begin(), (*it).end(), x));
    if ((*it).empty()) {
        List.erase(it);
    }
}

例題

P3369 【模板】普通平衡樹

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

template<typename T>
void print(T x, char c) {
   write(x);
   putchar(c);
}

list<vector<ll>> List;

using lit = list<vector<ll>>::iterator;
using vit = vector<ll>::iterator;

int lim;

lit find(const int &p) {
    int cnt = 0;
    for (lit it = List.begin(); it != List.end(); ++ it) {
        if ((*it).back() >= p) {
            return it;
        }
    }
}

void insert(int x) {
    lit it = find(x);
    (*it).emplace(lower_bound((*it).begin(), (*it).end(), x), x);
    if ((*it).size() > lim) {
        List.emplace(next(it), (*it).begin() + (lim / 2), (*it).end());
        (*it).erase((*it).begin() + (lim / 2), (*it).end());
    }
}

void erase(int x) {
    lit it = find(x);
    (*it).erase(lower_bound((*it).begin(), (*it).end(), x));
    if ((*it).empty()) {
        List.erase(it);
    }
}

int kth(int k) {
    for (vector<ll> it : List) {
        if (it.size() >= k) {
            return it[k - 1];
        } else {
            k -= it.size();
        }
    }
    return 0;
}

int num(int x) {
    int cnt = 0;
    for (vector<ll> it : List) {
        if (it.back() >= x) {
            cnt += lower_bound(it.begin(), it.end(), x) - it.begin() + 1;
            return cnt;
        } else {
            cnt += it.size();
        }
    }
}

int qpre(int x) {
    lit it = find(x);
    vit it1 = lower_bound((*it).begin(), (*it).end(), x);
    if (it1 == (*it).begin()) {
        -- it;
        return (*it).back();
    } else {
        -- it1;
        return (*it1);
    }
}

int qnxt(int x) {
    lit it = find(x);
    vit it1 = upper_bound((*it).begin(), (*it).end(), x);
    if (it1 == (*it).end()) {
        ++ it;
        return (*it).front();
    } else {
        return *it1;
    }
}

int n;

int main() {
    vector<ll> tmp;
    tmp.emplace_back(LLONG_MAX);
    List.emplace_back(tmp);
    n = read<int>();
    lim = sqrt(n);
    for (int i = 1, op, x; i <= n; ++ i) {
        op = read<int>(), x = read<int>();
        if (op == 1) {
            insert(x);
        }
        if (op == 2) {
            erase(x);
        }
        if (op == 3) {
            print(num(x), '\n');
        }
        if (op == 4) {
            print(kth(x), '\n');
        }
        if (op == 5) {
            print(qpre(x), '\n');
        }
        if (op == 6) {
            print(qnxt(x), '\n');
        }
    }
    return 0;
}