problem
给一个字符串，长度不超过 1e6，有两种操作：
- 在第 i 个字符的前面添加一个字符 ch
- 查询第 k 个位置是什么字符
操作的总数不超过 2000
solution
1、传统的数组所有数据在内存中是紧凑储存的，优点是定位快：O(1)，缺点是修改慢：O(n)
2、传统的链表每个节点只记录一个字符，优缺点与数组正好相反：定位慢 O(n)，修改快 O(1) 3、块状链表的每个节点记录的是 sqrt(n) 个信息，一个长度为 n 的字符串就被分成了 sqrt(n) 个。这样，查询和插入字符的操作就变成了 sqrt(n）级别的了，对于这题 2000 个操作来讲，时间复杂度还能忍受 4、在实际应用中，需维持块状链表的每个结点大小在[sqrt(n)/2,2∗sqrt(n)]，否则时间会退化的很厉害。（超过了就将一个结点分裂成两个）codes
#include#include const int maxn = 2000, maxlen = 1e6+10;//sqrt(1e6)struct Block_List{ struct Node{ char buff[maxn]; int size, next; void init(){ size = 0, next = -1; memset(buff,0,sizeof(buff)); } }List[maxn]; int head, tot; void init(char s[]){ head = tot = 0; List[tot++].init(); int cur = 0; for(int i = head; s[cur]; i = List[i].next){ for(int j = 0; j < maxn && s[cur]; j++,cur++){ List[i].buff[j] = s[cur]; List[i].size++; } if(s[cur]){ List[tot].init(); List[i].next = tot++; } } for(int i = head; i!=-1; i = List[i].next) if(List[i].size==maxn)Split(i); } void Split(int id){ List[tot].init(); for(int i = maxn/2; i < maxn; i++){ List[tot].buff[i-maxn/2] = List[id].buff[i]; List[tot].size++; List[id].buff[i] = 0; List[id].size--; } List[tot].next = List[id].next; List[id].next = tot++; } void Insert(int pos, char val){ int i; for(i = head; pos > List[i].size && List[i].next != -1; i = List[i].next) pos -= List[i].size; if(pos >= List[i].size)List[i].buff[List[i].size] = val; else { for(int j = List[i].size; j > pos; j--) List[i].buff[j] = List[i].buff[j-1]; List[i].buff[pos] = val; } List[i].size++; if(List[i].size==maxn)Split(i); } char Find(int pos){ int i; for(i = head; pos > List[i].size; i = List[i].next) pos -= List[i].size; return List[i].buff[pos-1]; }}Meow;char op[2], buff[maxlen];int pos;int main(){ scanf("%s",buff); Meow.init(buff); int n; scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%s",op); if(op[0]=='I'){ scanf("%s%d",buff,&pos); Meow.Insert(pos-1,buff[0]); }else { scanf("%d",&pos); printf("%c\n",Meow.Find(pos)); } } return 0;}