<span>POJ2887 Big String（块状数组）</span>
参考：http://blog.csdn.net/htt_h/article/details/44862813
题意：
给你一个不超过1e6的字符串，和不超过2000次的操作
操作分为两种：
1.将一个字符插入到某个位置的前面
2.询问当前位置的字符
思路：
学了一发块状数组，就是把1e6的原串分为1e3份，每份长度相同，
由于操作不超过两千次，那每一份的长度不会超过3e3，
可以开一个1e3*3e3的字符数组来存储串，开一个1e3的长度数组记录每部分的长度
这样就可以在较短的时间内完成插入和查找操作
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e3+10; char s[N*N],eg[N][N*3],in[2]; int l[N],n,m,x; void add(char ch,int x) { int nl=0,pn; for(int i=0;i<n;i++) { if(nl+l[i]>=x){pn=i;break;} if(i==n-1) {pn=n-1;break;} nl+=l[i]; } int p=min(l[pn],x-nl-1); for(int i=l[pn];i>p;i--) eg[pn][i]=eg[pn][i-1]; eg[pn][p]=ch; l[pn]++; } char query(int x) { int nl=0; for(int i=0;i<n;i++) { if(nl+l[i]>=x) return eg[i][x-nl-1]; nl+=l[i]; } } int main() { //freopen("in.txt","r",stdin); while(~scanf("%s",s)) { int len=strlen(s); int ave=(len+999)/1000; n=(len-1)/ave+1; for(int i=0;i<n;i++) l[i]=ave; for(int i=0;i<len;i++) eg[i/ave][i%ave]=s[i]; l[n-1]=(len-1)%ave+1; scanf("%d",&m); while(m--) { scanf("%s",in); if(in[0]=='Q') { scanf("%d",&x); printf("%c\n",query(x)); } else { scanf("%s%d",in,&x); add(in[0],x); } } } return 0; }
远景公司福利 157人发布
