[POJ 2887] Big String【块状链表】

  • 2018-03-01
  • 0
  • 0

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:

  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.

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) 的优秀复杂度。

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

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

此处假定合适的大小为 (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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai