给一个字符串，长度不超过 10，有两种操作：
1. 在第 i 个字符的前面添加一个字符 ch
2. 查询第 k 个位置是什么字符
操作的总数不超过 2000
如果直接模拟的话，移动到后面的数据量太大。我们分块的话，就可以优化，减少移动的量。 很典型的块状数组。块状数组的next指向的是一块，而不是一个。这里用整数代替了指针。
每一个块就是一个对象。这题用面向对象编程。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF=0x4fffffff;
const int EXP=1e-;
const int MS=; struct node
{
int size,next;
char str[MS];
void push(char ch)
{
str[size++]=ch;
}
void insert(int pos,char ch)
{
for(int i=size++;i>pos;i--)
str[i]=str[i-];
str[pos]=ch;
} }nodes[MS]; char S[*MS];
int SIZE,cnt,Q; void input()
{
scanf("%s",S);
scanf("%d",&Q);
int len=strlen(S);
SIZE=(int)sqrt(0.1+len+Q);
cnt=;
nodes[cnt].size=;
for(int i=;i<len;i++)
{
if(nodes[cnt].size>=SIZE)
{
nodes[cnt].next=cnt+;
nodes[++cnt].size=;
}
nodes[cnt].push(S[i]);
}
nodes[cnt].next=-;
} //设一个块的最大容量为2*SIZE，当满了就要从后面使用一块来补充
void updata(int id)
{
if(nodes[id].size<*SIZE) // 我们是在区间插入一个字符后在更新，所以要留一个位置
return ;
++cnt;
int i,j,k=nodes[id].size;
for(i=SIZE,j=;i<k;i++,j++)
nodes[cnt].str[j]=nodes[id].str[i];
nodes[cnt].size=j;
nodes[id].size=SIZE;
nodes[cnt].next=nodes[id].next;
nodes[id].next=cnt;
} void solve()
{
int i,j,pos;
char cmd[MS];
for(i=;i<Q;i++)
{
scanf("%s",cmd);
if(cmd[]=='Q')
{
scanf("%d",&pos);
for(j=;pos>nodes[j].size;j=nodes[j].next)
pos-=nodes[j].size;
printf("%c\n",nodes[j].str[pos-]);
}
else
{
scanf("%s%d",cmd,&pos);
for(j=;pos>nodes[j].size&&nodes[j].next!=-;j=nodes[j].next)
pos-=nodes[j].size;
nodes[j].insert(min(pos-,nodes[j].size),cmd[]);
updata(j);
}
}
} int main()
{
input();
solve();
return ;
}