POJ2887 Big String 孩子T飞了

题目只要求单点插入、单点查询

#include<cstdio>
#include<cstring>
using namespace std;
int allsize,nodenum,sqrtk;
struct node
{
	int size,next=-1;
	char data[2005];
}x[2005];
int find(int &pos)
{
	int i=0;
	while(x[i].size<pos)
	{
		pos-=x[i].size;
		i=x[i].next;
	}
	return i;
}
char query(int pos)
{
	int k=find(pos);
	return x[k].data[pos];
}
void split(int k)
{
	nodenum++;
	x[nodenum].next=x[k].next;
	x[k].next=nodenum;
	memcpy(x[nodenum].data,&x[k].data[x[k].size/2],x[k].size-x[k].size/2);
	x[nodenum].size=x[k].size-x[k].size/2;
	x[k].size/=2;
}
void insert(int pos,char ch)
{
	int k=find(pos);
	for(int i=x[k].size;i>=pos;i--)
		x[k].data[i+1]=x[k].data[i];
	x[k].data[pos]=ch;
	x[k].size++;
	allsize++;
	if(sqrtk*sqrtk<allsize)
		sqrtk++;
	if(x[k].size>=2*sqrtk)
		split(k);
}
int n,m;
char str[1000001];
int main()
{
	scanf("%s",str);
	m=strlen(str);
	for(int i=0;i<m;i++)
		insert(i,str[i]);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		char op;
		scanf(" %c",&op);
		if(op=='Q')
		{
			int pos;
			scanf("%d",&pos);
			pos--;
			printf("%c\n",query(pos));
		}
		if(op=='I')
		{
			int pos;
			char ch;
			scanf(" %c %d",&ch,&pos);
			pos--;
			insert(pos,ch);
		}
	}
}