[POJ 2887] Big String【块状链表】
Problem:
Time Limit: 1000MS | Memory Limit: 131072K |
Description
You are given a string and supposed to do some string manipulations.
Input
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:
- 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.
- 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.
Output
For each Q command output one line containing only the single character queried.
Sample Input
ab 7 Q 1 I c 2 I d 4 I e 2 Q 5 I f 1 Q 3
Sample Output
a d e
Source
POJ Monthly--2006.07.30, zhucheng
Solution:
题意是给定一个字符串,实现一种支持在第 p 位前插入字符 ch 以及询问第 p 位的数据结构。
我们知道数组是询问 O(1),插入/删除 O(n) 的,链表是询问 O(n),插入/删除 O(1) 的。
考虑将两者进行结合,采用分块的思想,构建出块状链表。
块状链表是链表套数组的数据结构,其整体是一个链表,而链表上每个节点都是一个数组。
当每个节点的数组元素个数为 O(n0.5) 级别时,节点数也为 O(n0.5) 级别。
此时遍历链表的复杂度为 O(n0.5),数据搬移的复杂度也为 O(n0.5),达到根号平衡。
所以块状链表可以做到询问 O(n0.5),插入/删除 O(n0.5) 的优秀复杂度。
进行插入/删除操作后,块状链表节点的数组元素数量变得可能过大/过小,影响效率。
此时我们考虑实现 split 和 merge 两个函数,自动进行分裂和合并来维持合适的大小。
此处假定合适的大小为 (n0.5 / 2, n0.5 * 2),链表使用双向链表实现。
注意指针版的程序要防止 split 和 merge 修改前驱后继时访问到 NULL 而导致 RE!!!
Code: O(L+NL0.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; }
发表评论