Ryan_<

先来看一道题~

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

　　1. 在第 i 个字符的前面添加一个字符 ch

　　2. 查询第 k 个位置是什么字符

操作的总数不超过 2000

多种数据结构可解.

而我们选择用数组与链表的结合物求解——

块状链表 登登登登~!

先贴代码(实现并不简洁啊..怎么又开启抄代码模式了呢,sigh)

const int N=2000,M=(int)1e6+10;//每块大小阈值 
struct node{
	char s[N];
	int next,siz;
	void init(){
		mec(s,0);
		next=-1;siz=0;
	}
}List[N];
int head,tot,q;
char str[M],ch[5];
void Split(int id)
{
	List[tot].init();
	for(int i=N/2;i<N;i++){
		List[tot].s[i-N/2]=List[id].s[i];
		List[tot].siz++;
		List[id].s[i]=0;
		List[id].siz--;
	}
	List[tot].next=List[id].next;
	List[id].next=tot++;
}
void init(char *str)
{
	head=tot=0;
	List[tot++].init();
	for(int i=0,cur=head;str[i];cur=List[cur].next){
		for(int j=0;j<N&&str[i];i++,j++){//j<N
			List[cur].s[j]=str[i];
			List[cur].siz++;
		}
		if(str[i]){
			List[tot].init();
			List[cur].next=tot++;
		}
	}
	for(int cur=head;cur!=-1;cur=List[cur].next)
		if(List[cur].siz==N) Split(cur);
}
void Insert(int pos,char val) 
{
	int cur=head;
	while(pos>List[cur].siz && List[cur].next!=-1)
		pos-=List[cur].siz,cur=List[cur].next;
	if(pos>=List[cur].siz) List[cur].s[List[cur].siz]=val;//添加到末尾
	else{//此时,pos是块内的位置 
		for(int i=List[cur].siz;i>pos;i--) List[cur].s[i]=List[cur].s[i-1];
		List[cur].s[pos]=val;//注意下标从0开始 
	}
	List[cur].siz++;
	if(List[cur].siz==N) Split(cur);
}
char Find(int pos)
{
	int cur=head;
	while(pos>List[cur].siz) 
		pos-=List[cur].siz,cur=List[cur].next;//顺次查找即可 
	return List[cur].s[pos-1];
}//每块中元素编号0~siz-1 
int main()
{
//	freopen(".in","r",stdin);
	scanf("%s",str);
	init(str);
	scanf("%d",&q);
	while(q--){
		char opt[5];
		int pos;
		scanf("%s",opt);
		if(opt[0]=='I'){
			scanf("%s%d",ch,&pos);
			Insert(pos-1,ch[0]);
		}
		else{
			scanf("%d",&pos);
			printf("%c\n",Find(pos));
		}
	}
	return 0;
}