块状链表 | Yuhang's Blog

例题：https://vjudge.net/problem/POJ-2887 要求支持字符串的插入（在第$x$位之前插入字符串$c$）、后缀（在整个字符串最后添加字符串$c$）、查询（查询当前第$x$位）操作。字符串长度1e6，操作数量2e3。

考虑基于数组的暴力算法：插入操作$O(n)$，后缀操作$O(1)$，查询操作$O(1)$。插入操作的复杂度太大，需要优化。考虑进行分块，把整个字符串分成平均长度大约是$B$的块，则一共有大约$N/B$个块；记录每块的长度。这时：

• 插入操作：先找到插入的位置所在的块，复杂度$O(N/B)$；然后在当前块进行暴力插入，复杂度$O(B)$。总复杂度$O(N/B + B)$。
• 后缀操作：保持记录最后一块，则可以对于最后一块$O(1)$完成。
• 查询操作：类似插入，先找到查询的位置所在的块，复杂度$O(N/B)$；不过下面立刻就可以进行$O(1)$查询。总复杂度$O(N/B)$。

可以看到我们需要最小化$N/B+B$，由基本不等式显然$B=\sqrt N$。 考虑实现。我们可以先定义一个结构体Node，表示每一块，其中需要记录的信息有下一块的指针、块大小、块的字符串内容。实现的方法则有后缀操作和暴力插入操作。但注意：我们必须保证块的大小不太大（这里因为不存在删除操作，块的大小不会太小），才能保证我们的前提“所有块的平均长度是$B$”。因此我们还需要实现一个“分裂”方法，其作用是当块的大小超过$2B$时，将块的后半部分分裂成一个新的块。这个分裂方法的复杂度是$O(B)$，在每次插入和后缀操作进行后都需要判断是否需要进行分裂。（如果可能存在块的大小太小的情况，理论上应当也实现“合并”方法。笔者臆测的实现方式：如果两个相邻的块大小都不超过$B/2$，则合并之。） 基于Node，我们可以定义第二个结构体LinkedNodes，记录头尾Node的指针和总大小，并实现插入、后缀和查询方法。详见代码。

#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>
#include<numeric>
#include<functional>
#include<climits>
#include<iomanip>
using namespace std;
#define rep(i,from,to) for(int i=(int)(from);i<=(int)(to);++i)
#define rev(i,from,to) for(int i=(int)(from);i>=(int)(to);--i)
#define For(i,to) for(int i=0;i<(int)(to);++i)
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define printCase(i) printf("Case %d: ", i)
#define endl '\n'
#define coutP(i) cout<<fixed<<setprecision(i)
// void dbg() {cout << "\n";}
// template<typename T, typename... A> void dbg(T a, A... x) {cout << a << ' '; dbg(x...);}
// #define logs(x...) {cout << #x << " -> "; dbg(x);}
#define mmst(a,x) memset(a, x, sizeof(a))
typedef long long ll;
typedef long double ld;
typedef double db;
inline ll read(){
    ll x=0;bool s=1;char c=getchar();
    while(c>'9'c<'0'){if(c=='-')s=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return s?x:~x+1;
}
void readch(char& ch) {
  do ch = getchar();
  while (!isalpha(ch));
}

const int N = 1e6;
const int SQN = 1e3;
struct LinkedNodes {
    struct Node {
        Node* nxt;
        int size;
        char d[SQN * 2 + 10];

        Node() { nxt = NULL; size = 0; }

        void split() {
            if (size < SQN * 2) return ;
            Node* q = new Node;
            rep(i, SQN + 1, size) {
                q->append(d[i]);
            }
            q->nxt = nxt;
            nxt = q;
            size = SQN;
        }

        void append(char c) {
            d[++size] = c;
            split();
        }

        void insert(char c, int x) {
            size++;
            rev(i, size, x + 1) { swap(d[i - 1], d[i]); }
            d[x] = c;
            split();
        }

        void output() {
            rep(i, 1, size) cout << d[i];
            cout << endl;
        }
    };

    Node* head;
    Node* tail;
    int size;

    LinkedNodes() { head = new Node; tail = head; size = 0; }

    char query(int x) {
        for (Node* p = head; p != NULL; p = p->nxt) {
            if (x <= p->size) return p->d[x];
            else x -= p->size;
        }
    }

    void append(char c) {
        while (tail->nxt != NULL) tail = tail->nxt;
        tail->append(c);
        size++;
    }

    void insert(char c, int x) { 
        for (Node* p = head; p != NULL; p = p->nxt) {
            if (x <= p->size) {
                p->insert(c, x);
                size++;
                break;
            } else {
                x -= p->size;
            }
        }
    }

    void output() {
        for (Node* p = head; p != NULL; p = p->nxt) {
            p->output();
        }
    }
};

char s[N + 100];
int main() {
    LinkedNodes* lns = new LinkedNodes();
    scanf("%s", s);
    int len = strlen(s);
    For(i, len) {
        lns->append(s[i]);
    }
    int m = read();
    while (m--) {
        char o; readch(o);
        if (o == 'I') {
            char c; int x;
            readch(c); x = read();
            if (x > lns->size) lns->append(c);
            else lns->insert(c, x);
        } else {
            int x = read();
            printf("%c\n", lns->query(x));
        }
    }
    return 0;
}