[POJ2887] Big String（块状链表）

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：http://poj.org/problem?id=2887
给一个字符串，要求两个操作：
I ch p：在这个字符串第p个字符前插入字符ch
Q p：查询第p个位置的字符

第一次写块状链表，还挺顺利的。。。
就是块大小调了几次wa了好几发。。。
块状链表比数组分块多了一个操作就是可以用拆分操作来支持插入操作。对于这个题来说就是当某个块中插入元素是块大小的2倍时，我们就可以把这个块拆成2个了。
我用的list可能常数可能比较大，但是非常好实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <list>
using namespace std;

const int maxn = 100100;
int bsize, len;
list<string> be;
char s[1001000];

void maintain() {
  for(list<string>::iterator p = be.begin(); p != be.end(); p++) {
    while(p->size() >= 2 * bsize) {
      string a = p->substr(0, bsize);
      string b = p->substr(bsize, p->length()-bsize);
      // cout <<*p<<" split: "<< a << " " << b << endl;
      *p = b;
      be.insert(p, a);
    }
  }
}

char query(int pos) {
  int tot = 0;
  for(list<string>::iterator p = be.begin(); p != be.end(); p++) {
    if(pos > tot + p->size()) {
      tot += p->size();
      continue;
    }
    for(int i = 0; i < p->size(); i++) {
      if(pos == tot+1) return (*p)[i];
      else tot++;
    }
  }
}

void insert(int pos, char* tmp) {
  int tot = 0;
  for(list<string>::iterator p = be.begin(); p != be.end(); p++) {
    if(pos > tot + p->size()) {
      tot += p->size();
      continue;
    }
    pos -= tot;
    p->insert(pos, tmp);
    break;
  }
  len++;
  maintain();
}

inline bool scan_d(int &num) {
  char in;bool IsN=false;
  in=getchar();
  if(in==EOF) return false;
  while(in!='-'&&(in<'0'||in>'9')) in=getchar();
  if(in=='-'){ IsN=true;num=0;}
  else num=in-'0';
  while(in=getchar(),in>='0'&&in<='9'){
    num*=10,num+=in-'0';
  }
  if(IsN) num=-num;
  return true;
}


signed main() {
  // freopen("in", "r", stdin);
  char cmd[5], tmp[1];
  int pos;
  scanf("%s", s);
  len = strlen(s);
  be.clear();
  bsize = 10000;
  be.push_back(s);
  maintain();
  int q;
  scan_d(q);
  while(q--) {
    scanf("%s", cmd);
    if(cmd[0] == 'Q') {
      scan_d(pos);
      printf("%c\n", query(pos));
    }
    else {
      scanf("%s", tmp);
      scan_d(pos);
      pos--;
      if(pos >= len) insert(len, tmp);
      else insert(pos, tmp);
    }
  }
}