editor.cpp 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<time.h>
  4. const int MAXL = 2*1024*1024+10;
  5. const int BLOCKSIZE = 20000;
  6. const int MAXBLOCK = MAXL/BLOCKSIZE*2+100;
  7. int min(int a,int b){return a<b?a:b;}
  8. int freelist[MAXBLOCK];
  9. int freepos;
  10. int newnode(){
  11. return freelist[freepos++];
  12. }
  13. void delnode(int t){
  14. freelist[--freepos]=t;
  15. }
  16. char data[MAXBLOCK][BLOCKSIZE];
  17. int count[MAXBLOCK];
  18. int next[MAXBLOCK];
  19. void find(int &p,int &b){
  20. for(b=0; b!=-1 && p>count[b]; b=next[b])p-=count[b];
  21. }
  22. void fillblock(int b,int n,char str[],int e){
  23. if(b==-1)return;
  24. next[b]=e;
  25. count[b]=n;
  26. memcpy(data[b], str, n);
  27. }
  28. void splite(int b,int p){
  29. if(b==-1 || p==count[b])return;
  30. int t=newnode();
  31. fillblock(t, count[b]-p, data[b]+p, next[b]);
  32. next[b]=t;
  33. count[b]=p;
  34. }
  35. void maintainlist(int b){
  36. for(; b!=-1; b=next[b])
  37. for(int t=next[b]; t!=-1 && count[b] + count[t] <= BLOCKSIZE; t=next[b]){
  38. memcpy(data[b]+count[b], data[t], count[t]);
  39. count[b]+=count[t];
  40. next[b]=next[t];
  41. delnode(t);
  42. }
  43. }
  44. void insert(int p,int n,char str[]){
  45. int b,t,i;
  46. find(p,b);
  47. splite(b,p);
  48. for(i=0; i+BLOCKSIZE <= n; i+=BLOCKSIZE){
  49. t=newnode();
  50. fillblock(t, BLOCKSIZE, str+i, next[b]);
  51. next[b]=t;
  52. b=t;
  53. }
  54. if(n-i){
  55. t=newnode();
  56. fillblock(t, n-i, str+i, next[b]);
  57. next[b]=t;
  58. }
  59. maintainlist(b);
  60. }
  61. void erase(int p,int n){
  62. int b,e;
  63. find(p,b);
  64. splite(b,p);
  65. for(e=next[b]; e!=-1 && n>count[e]; e=next[e])n-=count[e];
  66. splite(e,n);
  67. e=next[e];
  68. for(int t=next[b]; t!=e; t=next[b]){
  69. next[b]=next[t];
  70. delnode(t);
  71. }
  72. maintainlist(b);
  73. }
  74. void get(int p,int n,char str[]){
  75. int b,t,i;
  76. find(p,b);
  77. i=min(n, count[b]-p);
  78. memcpy(str, data[b]+p, i);
  79. for(t=next[b]; t!=-1 && i + count[t] <= n; i+=count[t],t=next[t])
  80. memcpy(str+i, data[t], count[t]);
  81. if(n-i && t!=-1)memcpy(str+i, data[t], n-i);
  82. str[n]='\0';
  83. }
  84. void init(){
  85. freopen("editor.in","r",stdin);
  86. freopen("editor.out","w",stdout);
  87. for(int i=1; i<MAXBLOCK; ++i)freelist[i]=i;
  88. freepos=1;
  89. next[0]=-1;
  90. count[0]=0;
  91. }
  92. char str[MAXL];
  93. int cur=0;
  94. void solve(){
  95. int t,k,n;char order[10],c;
  96. scanf("%d",&t);
  97. for(cur=0; t; --t){
  98. scanf("%s",order);
  99. switch(order[0]){
  100. case 'M': scanf("%d",&k);cur=k;break;
  101. case 'I':
  102. scanf("%d",&n);
  103. for(int i=0; i<n; ++i){
  104. scanf("%c",&c);
  105. str[i]=c;
  106. if(c<32 || c>126)--i;
  107. }
  108. insert(cur, n, str);
  109. break;
  110. case 'D': scanf("%d",&n);erase(cur, n);break;
  111. case 'G': scanf("%d",&n);get(cur, n, str);printf("%s\n",str);break;
  112. case 'P': --cur;break;
  113. case 'N': ++cur;break;
  114. }
  115. }
  116. fclose(stdin);
  117. fclose(stdout);
  118. }
  119. int main(){
  120. init();
  121. solve();
  122. fprintf(stderr, "%.2lf\n", clock()/(double)CLOCKS_PER_SEC);
  123. }