很明显要用块状链表。
我感觉我的代码没问题，但是WA了。还麻烦各位帮我看看，解释在代码注释里面。谢谢了！
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
struct node
{
char t[3001];//最多在一块链表里面插入2000个字符，而一块链表一开始最多有1000个字符。
int len;
node *nxt;
}a[1003];
int n,ret,m,now,i,j,ind;
char ch,s[1000001],op;
int main()
{
node *p;
scanf("%s",s);
m=strlen(s);
ret=sqrt((double)m);
for(i=ret;i<=m;i+=ret)
{
for(j=i-ret;j<i;++j)a[now].t[a[now].len++]=s[j];
++now;
}
if(i!=m+ret)
{
i-=ret;
for(j=i;j<m;++j)a[now].t[a[now].len++]=s[i];//分块存储，调过，没问题。
}
else --now;//链表的范围是0~now。
for(i=0;i<now;++i)a[i].nxt=&a[i+1];
a[now].nxt=NULL;//最后一块链表指向空指针。
scanf("%d",&n);
while(n--)
{
getchar(),p=&a[0],scanf("%c",&op),getchar();//这里有很多getchar，看上去很荒谬，但实际上是对的……
if(op=='I')
{
scanf("%c%d",&ch,&ind);
if(ind>m)ind=m+1;
while(p->nxt!=NULL&&ind>p->len)ind-=p->len,p=p->nxt;//如果已经是最后一块了，就不能往后，否则继续查找。
--ind;//因为我链表里面的t数组是0~(len-1)的，所以这里--ind。
for(i=p->len;i>ind;--i)p->t[i]=p->t[i-1];//数组的插入操作。
p->t[ind]=ch,++p->len,++m;//插入ch并更新这块链表的长度和总长度。
}
else
{
scanf("%d",&ind);
while(p->nxt!=NULL&&p->len)ind-=p->len,p=p->nxt;
printf("%c\n",p->t[ind-1]);//同上，下标应该是ind-1。
}
}//样例能过。
return 0;
}
