Big String 块状数组（或者说平方分割）

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Big String 　

给一个字符串，长度不超过 10⁶，有两种操作：

　　1. 在第 i 个字符的前面添加一个字符 ch

　　2. 查询第 k 个位置是什么字符

操作的总数不超过 2000

如果直接模拟的话，移动到后面的数据量太大。我们分块的话，就可以优化，减少移动的量。很典型的块状数组。块状数组的next指向的是一块，而不是一个。这里用整数代替了指针。

每一个块就是一个对象。这题用面向对象编程。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <string>
  7 #include <vector>
  8 #include <set>
  9 #include <map>
 10 #include <stack>
 11 #include <queue>
 12 #include <sstream>
 13 #include <iomanip>
 14 using namespace std;
 15 typedef long long LL;
 16 const int INF=0x4fffffff;
 17 const int EXP=1e-5;
 18 const int MS=2100;
 19 
 20 struct node
 21 {
 22     int size,next;
 23     char str[MS];
 24     void push(char ch)
 25     {
 26         str[size++]=ch;
 27     }
 28     void insert(int pos,char ch)
 29     {
 30         for(int i=size++;i>pos;i--)
 31             str[i]=str[i-1];
 32         str[pos]=ch;
 33     }
 34 
 35 }nodes[MS];
 36 
 37 char S[500*MS];
 38 int SIZE,cnt,Q;
 39 
 40 void input()
 41 {
 42     scanf("%s",S);
 43     scanf("%d",&Q);
 44     int len=strlen(S);
 45     SIZE=(int)sqrt(0.1+len+Q);
 46     cnt=0;
 47     nodes[cnt].size=0;
 48     for(int i=0;i<len;i++)
 49     {
 50         if(nodes[cnt].size>=SIZE)
 51         {
 52             nodes[cnt].next=cnt+1;
 53             nodes[++cnt].size=0;
 54         }
 55         nodes[cnt].push(S[i]);
 56     }
 57     nodes[cnt].next=-1;
 58 }
 59 
 60 //设一个块的最大容量为2*SIZE，当满了就要从后面使用一块来补充
 61 void updata(int id)
 62 {
 63     if(nodes[id].size<2*SIZE)    // 我们是在区间插入一个字符后在更新，所以要留一个位置
 64         return ;
 65     ++cnt;
 66     int i,j,k=nodes[id].size;
 67     for(i=SIZE,j=0;i<k;i++,j++)
 68         nodes[cnt].str[j]=nodes[id].str[i];
 69     nodes[cnt].size=j;
 70     nodes[id].size=SIZE;
 71     nodes[cnt].next=nodes[id].next;
 72     nodes[id].next=cnt;
 73 }
 74 
 75 void solve()
 76 {
 77     int i,j,pos;
 78     char cmd[MS];
 79     for(i=0;i<Q;i++)
 80     {
 81         scanf("%s",cmd);
 82         if(cmd[0]=='Q')
 83         {
 84             scanf("%d",&pos);
 85             for(j=0;pos>nodes[j].size;j=nodes[j].next)
 86                 pos-=nodes[j].size;
 87             printf("%c
",nodes[j].str[pos-1]);
 88         }
 89         else
 90         {
 91             scanf("%s%d",cmd,&pos);
 92             for(j=0;pos>nodes[j].size&&nodes[j].next!=-1;j=nodes[j].next)
 93                 pos-=nodes[j].size;
 94             nodes[j].insert(min(pos-1,nodes[j].size),cmd[0]);
 95             updata(j);
 96         }
 97     }
 98 }
 99 
100 int main()
101 {
102     input();
103     solve();
104     return 0;
105 }