You are given a string and supposed to do some string manipulations.

The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000.

The second line contains the number of manipulation commands N (0 < N ≤ 2,000). The following N lines describe a command each. The commands are in one of the two formats below:

1. I ch p: Insert a character ch before the p-th character of the current string. If p is larger than the length of the string, the character is appended to the end of the string.
2. Q p: Query the p-th character of the current string. The input ensures that the p-th character exists.

All characters in the input are digits or lowercase letters of the English alphabet.

For each Q command output one line containing only the single character queried.

POJ Monthly--2006.07.30, zhucheng

Solution:

题意是给定一个字符串，实现一种支持在第 p 位前插入字符 ch 以及询问第 p 位的数据结构。

我们知道数组是询问 O(1)，插入/删除 O(n) 的，链表是询问 O(n)，插入/删除 O(1) 的。

考虑将两者进行结合，采用分块的思想，构建出块状链表。

块状链表是链表套数组的数据结构，其整体是一个链表，而链表上每个节点都是一个数组。

当每个节点的数组元素个数为 O(n^0.5) 级别时，节点数也为 O(n^0.5) 级别。

此时遍历链表的复杂度为 O(n^0.5)，数据搬移的复杂度也为 O(n^0.5)，达到根号平衡。

所以块状链表可以做到询问 O(n^0.5)，插入/删除 O(n^0.5) 的优秀复杂度。

进行插入/删除操作后，块状链表节点的数组元素数量变得可能过大/过小，影响效率。

此时我们考虑实现 split 和 merge 两个函数，自动进行分裂和合并来维持合适的大小。

此处假定合适的大小为 (n^0.5 / 2, n^0.5 * 2)，链表使用双向链表实现。

注意指针版的程序要防止 split 和 merge 修改前驱后继时访问到 NULL 而导致 RE！！！

Code: O(L+NL^0.5) [3644K, 391MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

char str[1000002], opt[5];
int N, p, len, blsize, topbin = 0;

struct Node{
	char val[2002];
	int size;
	Node *pre, *suc;
	
	inline void clear() {size = 0, pre = suc = NULL;}
} pool[2002], *bin[2002];


inline Node* newNode(){
	static int topp = 0;
	Node *node = topbin ? bin[--topbin] : &pool[topp++];
	return node->clear(), node;
}

inline void delNode(Node *node) {bin[topbin++] = node;}

inline void split(Node *cur){
	Node *o = newNode();
	o->size = cur->size - (cur->size >> 1), cur->size = cur->size >> 1;
	o->suc = cur->suc, o->pre = cur, cur->suc = o;
	if(o->suc) o->suc->pre = o;  // Beware of the NULL pointer
	memcpy(o->val, cur->val + cur->size, sizeof(char) * o->size);
}

inline void merge(Node *cur, Node *o){
	memcpy(cur->val + cur->size, o->val, sizeof(char) * o->size);
	cur->size += o->size;
	cur->suc = o->suc;
	if(cur->suc) cur->suc->pre = cur;  // Beware of the NULL pointer
	delNode(o);
}

inline void maintain(Node *cur){
	if(cur->size >= blsize << 1) split(cur);
	else if(cur->suc && cur->size + cur->suc->size < blsize << 1) merge(cur, cur->suc);
	else if(cur->pre && cur->pre->size + cur->size < blsize << 1) merge(cur->pre, cur);
}

inline Node* build(char *str, int len){
	Node *head = newNode(), *cur = head;
	for(register int i = 0; i < len; i++){
		cur->val[cur->size++] = str[i];
		if(cur->size == blsize) cur->suc = newNode(), cur->suc->pre = cur, cur = cur->suc;
	}
	return head;
}

inline void insert(Node *cur, int pos, char v){
	while(cur->suc && pos > cur->size) pos -= cur->size, cur = cur->suc;
	if(pos > cur->size) pos = cur->size + 1;  // Exceed end of the string
	for(register int i = cur->size - 1; i >= pos - 1; i--) cur->val[i + 1] = cur->val[i];
	cur->val[pos - 1] = v, cur->size++;
	maintain(cur);
}

inline char query(Node *cur, int pos){
	while(pos > cur->size) pos -= cur->size, cur = cur->suc;
	return cur->val[pos - 1];
}

int main(){
	scanf("%s", str), len = strlen(str);
	blsize = int(sqrt(len));
	Node *head = build(str, len);
	scanf("%d", &N);
	while(N--){
		scanf("%s", opt);
		if(*opt == 'Q') scanf("%d", &p), printf("%c\n", query(head, p));
		else if(*opt == 'I') scanf("%s%d", opt, &p), insert(head, p, opt[0]);
	}
	return 0;
}