块状链表

· · 个人记录

块状链表平衡了数组和链表的优缺点，是单点插入（链表），单点查询（数组）等操作的根号算法。

由于本人比较弱，现在只给单点插入，单点查询的假的块状链表代码。（其实还可以干好多事）

简单版

CF455D Serega and Fun

链表好题

当然能想到块状链表。但不用那么复杂，只要链表+分块就好了。这是因为每次块内的元素个数不变，不会复杂度退化，因此不用暴力重建。

主要是链表的细节，要注意分清链表内节点编号和节点的值！！

注意建立哨兵节点防止越界（莫名变0）。这个题建哨兵非常方便有用！

Code: 

int a[N], nxt[N], pre[N], blong[N];
int st[NN], ed[NN], cnt[NN][N], stid[NN];
int m, ans;
inline int find(int x) {
    int bk = blong[x];
    int id = stid[bk], nwx = st[bk];
    while (nwx != x)    id = nxt[id], nwx++;
    return id;
}

int main() {

    init();

    read(m);
    register int l, r, type, k;
    while (m--) {
        read(type); read(l); read(r);
        l = (l + ans - 1) % n + 1;
        r = (r + ans - 1) % n + 1;
        if (l > r)  swap(l, r);
        if (type == 1) {
            if (l == r) continue;
            int lid = find(l), rid = find(r);
            if (blong[l] == blong[r]) {
                if (l == st[blong[l]])  stid[blong[l]] = rid;
                pre[nxt[rid]] = pre[rid]; clear();
                nxt[pre[lid]] = rid; clear();
                nxt[pre[rid]] = nxt[rid]; clear();
                pre[rid] = pre[lid];
                pre[lid] = rid;
                nxt[rid] = lid;
            } else {
                if (l == st[blong[l]])  stid[blong[l]] = rid;
                if (r == st[blong[r]])  stid[blong[r]] = nxt[rid];
                pre[nxt[rid]] = pre[rid];
                nxt[pre[lid]] = rid;
                nxt[pre[rid]] = nxt[rid];
                pre[rid] = pre[lid];
                pre[lid] = rid;
                nxt[rid] = lid;

                cnt[blong[r]][a[rid]]--;
                cnt[blong[l]][a[rid]]++;
                for (register int i = blong[l] + 1; i <= blong[r]; ++i) {
                    register int nwid = stid[i];
                    register int preid = pre[nwid];
                    cnt[i - 1][a[preid]]--;
                    cnt[i][a[preid]]++;
                    stid[i] = preid;
                }
            }
            clear();
        } else {
            read(k);
            k = (k + ans - 1) % n + 1;
            int lid = find(l), rid = find(r);
            ans = 0;
            if (blong[l] == blong[r]) {
                int nwid = lid;
                while (nwid != rid) {
                    ans += a[nwid] == k;
                    nwid = nxt[nwid];
                }
                ans += a[rid] == k;
            } else {
                int nwid = lid;
                while (nwid != stid[blong[l] + 1]) {
                    ans += a[nwid] == k;
                    nwid = nxt[nwid];
                }
                for (register int i = blong[l] + 1; i <= blong[r] - 1; ++i) {
                    ans += cnt[i][k];
                }
                nwid = stid[blong[r]];
                while (nwid != rid) {
                    ans += a[nwid] == k;
                    nwid = nxt[nwid];
                }
                ans += a[rid] == k;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

#6282. 数列分块入门 6

//由于只需支持单点插入单点查询，这里用根号个vector来降低复杂度.
#define int long long
vector<int> v[NN];
inline pair<int, int> query(int xx) {//return v[first][second]( = a[xx]);
    int x = 1;
    while (xx > v[x].size())
        xx -= v[x].size(), ++x;
    return make_pair(x, xx - 1);
}
int tp[N], top;
inline void rebuild() {
    top = 0;
    for (register int i = 1; v[i].size(); ++i) {
        for (vector<int>::iterator it = v[i].begin(); it < v[i].end(); ++it)
            tp[++top] = *it;
        v[i].clear();
    }
    block = sqrt(top);
    for (register int i = 1; i <= top; ++i) 
        v[(i - 1) / block + 1].push_back(tp[i]);
}
inline void add(int xx, int num) {
    pair<int, int> tmp = query(xx);
    v[tmp.first].insert(v[tmp.first].begin() + tmp.second, num);
    if (v[tmp.first].size() > (block << 4)) {
        rebuild();
    }
}
signed main() {
    read(n);
    block = sqrt(n);
    int opt, ll, rr, cc;
    for (register int i = 1; i <= n; ++i) {
        read(cc);
        v[(i - 1) / block + 1].push_back(cc);
    }
    pair<int, int> res;
    for (register int q = 1; q <= n; ++q) {
        read(opt); read(ll); read(rr); read(cc);
        if (!opt) add(ll, rr);
        else {
            res = query(rr);
            printf("%lld\n", v[res.first][res.second]);
        }
    }
    return 0;
}

Continued...