题意：给一个字符串（<=1000000)和n个操作（<2000），每个操作可以在某个位置插入一个字符，或者查询该位置的字符。问查询结果。
思路：块状数组。
如果将原来的字符串都存在一起，每次插入肯定会超时。
而操作数比较少，考虑使用分块法。假设原字符串长度为L，则取每块长度l=sqrt（L）。这样每次插入，我们需要用sqrt(L)的时间找到对应的块，再用sqrt(L)在该块进行插入。查询同样需要sqrt(L)找到该块，如果用数组实现可以O（1）找到目标元素。（我尝试用stl链表来做，结果超时了）
这样最坏的情况下，一个块最多有2000个字符，当然操作不会超时，但是数组要开得足够大。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <list>
#define ll long long
using namespace std;
int Maxn, N ;
];
struct BlockList
{
int size;
];
int at(int pos)
{
return dat[pos];
}
void insert(int pos,char c)
{
];
dat[pos]=c;
}
void push_back(char c)
{
dat[++size]=c;
}
};
BlockList block[];
char query(int s,int p)
{
return block[s].at(p);
}
void insert(int s,int p,char c)
{
p=min(p,block[s].size+);
block[s].insert(p,c);
}
void maintain()
{
; i<=Maxn; ++i)
sum[i]=sum[i-]+block[i].size;
}
void MyInsert(int pos,char c)
{
,sum++Maxn,pos)-(sum);
insert(p,pos-sum[p-],c);
maintain();
}
int MyQuery(int pos)
{
,sum++Maxn,pos)-(sum);
]);
}
];
void init()
{
int len=strlen(str)+N;
Maxn=sqrt(len*;
; str[i]; ++i)
block[i/Maxn+].push_back(str[i]);
maintain();
}
int main()
{
gets(str);
int pos;
],s[];
scanf("%d",&N);
init();
while(N--)
{
scanf("%s",p);
]=='I')
{
scanf("%s%d",s,&pos);
MyInsert(pos,s[]);
}
else
{
scanf("%d",&pos);
printf("%c\n",MyQuery(pos));
}
}
;
}