Big String

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 7053		Accepted: 1684

Description

You are given a string and supposed to do some string manipulations.

Input

The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000.

The second line contains the number of manipulation commands N (0 < N ≤ 2,000). The following N lines describe a command each. The commands are in one of the two formats below:

1. I ch p: Insert a character ch before the p-th character of the current string. If p is larger than the length of the string, the character is appended to the end of the string.
2. Q p: Query the p-th character of the current string. The input ensures that the p-th character exists.

All characters in the input are digits or lowercase letters of the English alphabet.

Output

For each

 

Q

 command output one line containing only the single character queried.

Sample Input

ab7Q 1I c 2I d 4I e 2Q 5I f 1Q 3

Sample Output

ade

Source

, zhucheng

题目大意 

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

    1、Q x(0 < x <= len(s)) 表示查询当前串中第x个字符

    2、I c x(c为字母 0 < x <= len(s)+1)表示在第x个位置插入c字符 x == len+1表示在串尾插入

操作的总数不超过 2000

做法分析

    块状链表裸题。详见代码

#include
     
      #include
      
       #include
       
        #define m(s) memset(s,0,sizeof s)using namespace std;const int N=1010;int l[N],n,m;char s[N*N],eg[N][N*3];void insert(int x,char c){    int n1=0,p1,pn=n;    for(int i=1;i<=n;i++){        if(n1+l[i]>=x){pn=i;break;}        if(i==n) break;        n1+=l[i];    }    p1=x-n1;l[pn]=max(p1,l[pn]+1);    for(int i=l[pn];i>p1;i--) eg[pn][i]=eg[pn][i-1];    eg[pn][p1]=c;}void query(int x){    int n1=0,p1,pn=n;    for(int i=1;i<=n;i++){        if(n1+l[i]>=x){pn=i;break;}        n1+=l[i];    }    p1=x-n1;    printf("%c\n",eg[pn][p1]);}void work(){    scanf("%d",&m);    int len=strlen(s),ave;    ave=(len+999)/1000;    n=(len-1)/ave+1;    for(int i=0;i