Big String
Time Limit: 1000MS Memory Limit: 131072K
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:
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.
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
ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3
Sample Output
a
d
e
Source
POJ Monthly–2006.07.30, zhucheng
/*
块状数组裸题.
把链表和数组的特性结合起来.
各个块互不影响(包括长度).
定位的时候看在哪一块就可以了.
各种复杂度都是√n.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 1000010
#define MAXM 1001
using namespace std;
int n,m,k,ans,tot,len[MAXN];
char s[MAXM][MAXM*10],ch[3],ss[MAXN];
void add(char c,int x)
{
int l1=0,p=n;
for(int i=1;i<=n;i++)
{
if(l1+len[i]>=x||i==n) {p=i;break;}
l1+=len[i];
}
int pos=x-l1;len[p]=max(pos,len[p]+1);
for(int i=len[p];i>pos;i--) s[p][i]=s[p][i-1];
s[p][pos]=c;
return;
}
char query(int x)
{
int l1=0,p=n;
for(int i=1;i<=n;i++)
{
if(l1+len[i]>=x) {p=i;break;}
l1+=len[i];
}
return s[p][x-l1];
}
void slove()
{
memset(len,0,sizeof len);
memset(s,0,sizeof s);
scanf("%d",&k);
int l=strlen(ss),x=(l+999)/1000;
n=(l-1)/x+1;
for(int i=0;i<l;i++)
s[i/x+1][i%x+1]=ss[i],len[i/x+1]++;
while(k--)
{
scanf("%s",ch);
if(ch[0]=='Q') scanf("%d",&x),printf("%c\n",query(x));
else scanf("%s%d",ch,&x),add(ch[0],x);
}
}
int main()
{
while(~scanf("%s",ss)) slove();
}