Big String（poj 2887）

题意：

给你一个不超过1e6的字符串，和不超过2000次的操作

操作分为两种：

1.将一个字符插入到某个位置的前面

2.询问当前位置的字符

/*
  块状链表模板水题（我的智商也就能做这种题了）。
  观察题目，我们发现询问次数是很少的，所以可以考虑暴力？
  很明显暴力就会gg，但是可以把这n个字母分为√n 块，然后查找的时候先用√n的时间找出在哪一块，
  然后只在这一块中找就行了。 
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1010
using namespace std;
int l[N],n,m,len;
char s[N*N],eg[N][N*3];
void add(char c,int x){
    int n1=0,pn=n;
    for(int i=1;i<=n;i++){
        if(n1+l[i]>=x){pn=i;break;}
        if(i==n)break;
        n1+=l[i];
    }
    int pos=x-n1;l[pn]=max(pos,l[pn]+1);
    for(int i=l[pn];i>pos;i--)
        eg[pn][i]=eg[pn][i-1];
    eg[pn][pos]=c;
}
void query(int x){
    int n1=0,pn=n;
    for(int i=1;i<=n;i++){
        if(n1+l[i]>=x){pn=i;break;}
        n1+=l[i];
    }
    int pos=x-n1;
    printf("%c
",eg[pn][pos]);
}
void work(){
    scanf("%d",&m);
    int len=strlen(s),ave;
    ave=(len+999)/1000;
    n=(len-1)/ave+1;
    for(int i=0;i<len;i++) eg[i/ave+1][i%ave+1]=s[i],l[i/ave+1]++;
    while(m--){
        char c[2];int x;
        scanf("%s",c);
        if(c[0]=='Q') scanf("%d",&x),query(x);
        else scanf("%s%d",c,&x),add(c[0],x);
    }
}
int main(){
    while(~scanf("%s",s)){
        memset(l,0,sizeof(l));
        memset(eg,0,sizeof(eg));
        work();
    }
    return 0;
}