河南网站建设SEO优化制作设计公司/百度网址入口

题意：给出一字符串，然后有两种操作，在某个位置后面插入某个字符，查询更新后字符串中某个位置的字符。

　　这个题，需要用到一个神奇的数据结构：块状链表；

　　推荐论文可自学：对块状链表的一点研究；

　　题中提到的两种操作都是非常理论的，可以直接套用块状链表的功能。高级的块状链表的维护操作会对根据某个块的大小做出裁决，是保留，是分裂，亦或是合并。但是这题的操作数量最多有2000。完全没有必要用这些操作，毕竟对于2000这样的数，计算机数着还是轻而易举的。而且题目的数据并没有卡维护，所以大胆省略代码，放弃一些时间也无所谓。（当然，如果大神追求完美的话，加上更好）；

下面上代码：

 1 //%%%%%%%%%%%%%尹兄 
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 const int MAXN=2005;
 9 const int MAXM=1000005;
10 struct Blist{
11     int siz;char da[MAXN];
12     void pushback(char c){
13         siz++;da[siz]=c;
14     }
15     void insert(int pos,char c){
16         for(int i=siz+1;i>pos;i--) da[i]=da[i-1];
17         da[pos]=c;siz++;
18     }
19     char getdata(int pos){
20         return da[pos];
21     }
22 }blist[MAXN];
23 char ch[MAXM];int sum[MAXM],num,n,m;
24 void maintain(){
25     for(int i=1;i<=num;i++) sum[i]=sum[i-1]+blist[i].siz;
26 }
27 void init(){
28     num=sqrt((n+m)*1.0)+1;
29     for(int i=0;i<n;i++) blist[i/num+1].pushback(ch[i]);maintain();
30 }
31 char query(int pos,int no){
32     return blist[no].getdata(pos);
33 }
34 void insert(int pos,int no,char c){
35     blist[no].insert(pos,c);
36 }
37 char myquery(int pos){
38     int p=lower_bound(sum+1,sum+1+num,pos)-sum;
39     return query(pos-sum[p-1],p);
40 }
41 void myinsert(char c,int pos){
42     int p=lower_bound(sum+1,sum+1+num,pos)-sum;
43     insert(pos-sum[p-1],p,c);maintain();
44 }
45 int main(){
46     scanf("%s",ch);n=strlen(ch);scanf("%d",&m);
47     init();char s[3],c[3];int p;
48     while(m--){
49         scanf("%s",s);
50         if(s[0]=='Q')
51         scanf("%d",&p),printf("%c\n",myquery(p));
52         else scanf("%s%d",c,&p),myinsert(c[0],p);
53     }
54     return 0;
55 }

转载于:https://www.cnblogs.com/Alan-Luo/articles/9452009.html