P4008 文本编辑器NOI2003

admin

仔细检查了自己的程序，一点问题也没有呀，为什么9个都是TLE呢？没得法，去LYDSY找到1507，下载了它的传输数据，用cena对比，第一组数据2003个操作，一开始就是一个1000000的大字符串，我的程序运行370秒！！！，网上题解上的程序只要0.74秒！彻底挫败了！考虑到此题数据输入量确实大，一向不喜欢scanf和printf的我还勉为其难没有用cin cout还有意识的使用了getchar。问题出在哪里呢？要是真的考试，我就太冤了！整整一个完全正确的题目最后只有10分，想起来就是一身的冷汗！
开始分步调试，那个2003个操作一上来就是1000000个字符串的插入建树，我就看这一段。
我花了100秒，别人的花了0.74秒！

admin

原因揭晓！  s=s+ch大大拖慢了速度 所以改成字符数组，把build 函数里面的s参数去掉，速度就上来了！ 我一身的冷汗呀。要是考试就全完了

admin

1. #include <bits/stdc++.h>
   
2. using namespace  std;
   
3. const  int mm=2100000;
   
4. struct Node
   
5. {
   
6.         char val;
   
7.         int fa,s[2],sz;
   
8. } a[mm];
   
9. int root,tot,curpos,offset;
   
10. char s[mm];
    
11. void ArrayPr()   /// 调试监视使用
    
12. {
    
13.         cout<<endl<<"  i ";
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
15.         cout<<endl<<"val ";
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
17.         cout<<endl<<" s0 ";
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
19.         cout<<endl<<" s1 ";
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
21.         cout<<endl<<" fa ";
    
22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
23.         cout<<endl<<" sz ";
    
24.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
25.         cout<<endl;
    
26. }
    
27. void pushup(int x)
    
28. {
    
29.         int l=a[x].s[0],r=a[x].s[1];
    
30.         a[x].sz=a[l].sz+a[r].sz+1;
    
31. }
    
32. int son(int x)
    
33. {
    
34.         int y=a[x].fa;
    
35.         return a[y].s[1]==x;
    
36. }
    
37. void R(int x)
    
38. {
    
39.         int y=a[x].fa;
    
40.         int z=a[y].fa;
    
41.         int k=son(x);
    
42.         int v=a[x].s[k^1];
    
43.         a[y].s[k]=v,a[v].fa=y;
    
44.         a[z].s[son(y)]=x,a[x].fa=z;
    
45.         a[x].s[k^1]=y,a[y].fa=x;
    
46.         pushup(y),pushup(x);
    
47. }
    
48. void Splay(int x,int rt=root)  ///把x旋到rt的位置 默认rt是根
    
49. {
    
50.         rt=a[rt].fa;
    
51.         int y,z;
    
52.         while(a[x].fa!=rt)
    
53.                 {
    
54.                         y=a[x].fa,z=a[y].fa;;
    
55.                         if(z!=rt)
    
56.                                 if(son(x)==son(y))R(y);
    
57.                                 else R(x);
    
58.                         R(x);
    
59.                 }
    
60.         if(rt==0)root=x;
    
61. }
    
62. int Build(int l,int r) ///把s串L-R之间的建树
    
63. {
    
64.         if (l>r)return 0;
    
65.         if (l==r)
    
66.                 {
    
67.                         a[offset+l].sz=1;
    
68.                         return l;
    
69.                 }
    
70.         if (l<r)
    
71.                 {
    
72.                         int m=(l+r)/2;
    
73.                         int tl=0,tr=0;
    
74.                         if (m-1>=l)
    
75.                                 {
    
76.                                         tl=Build(l,m-1),a[offset+tl].fa=offset+m,a[offset+m].s[0]=offset+tl;
    
77.                                 }
    
78.                         if (m+1<=r)
    
79.                                 {
    
80.                                         tr=Build(m+1,r),a[offset+tr].fa=offset+m,a[offset+m].s[1]=offset+tr;
    
81.                                 }
    
82.                         a[offset+m].sz=r-l+1;
    
83.                         return m;
    
84.                 }
    
85. }
    
86. int Getkth(int rt, int x) ///在RT子树中找第k小
    
87. {
    
88.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
    
89.         if(l+1==x)
    
90.                 {
    
91.                         Splay(rt,root);
    
92.                         return rt;
    
93.                 }
    
94.         if(l+1>x) return Getkth(a[rt].s[0], x); ///左儿子里去找
    
95.         if(l+1<x) return Getkth(a[rt].s[1], x-(l+1));
    
96. }
    
97. 
    
98. void NewEmpty()/// 建新的假树
    
99. {
    
100.         a[1].val=a[2].val='@';
     
101.         a[1].s[0]=a[2].s[0]=a[2].s[1]=0,a[1].s[1]=2;
     
102.         a[1].fa=0,a[2].fa=1;
     
103.         a[1].sz=2,a[2].sz=1;
     
104.         root=1,tot=2,curpos=0;
     
105. }
     
106. void BSTPr(int x)
     
107. {
     
108.         int l=a[x].s[0],r=a[x].s[1];
     
109.         if (l>0) BSTPr(l);
     
110.         printf("%c",a[x].val);
     
111.         if (r>0) BSTPr(r);
     
112. 
     
113. }
     
114. int main()
     
115. {
     
116. 
     
117.         int n;
     
118.         scanf("%d",&n);
     
119.         NewEmpty();
     
120.         while (n--)
     
121.                 {
     
122.                         char opt[10];
     
123.                         scanf("%s", opt);
     
124.                         if (opt[0]=='M')
     
125.                                 {
     
126.                                         int k;
     
127.                                         scanf("%d",&k);
     
128.                                         curpos=k;
     
129.                                 }
     
130. 
     
131.                         if (opt[0]=='I')
     
132.                                 {
     
133.                                         int l,i=1;
     
134.                                         scanf("%d",&l);
     
135.                                         char ch;
     
136.                                          s[0]='#';
     
137.                                         while (i<=l)
     
138.                                                 {
     
139.                                                         ch=getchar();
     
140.                                                         while(ch<32||ch>126) ch=getchar();
     
141.                                                         s[i++]=ch;
     
142.                                                 }
     
143.                                         offset=tot;
     
144.                                         tot+=l;
     
145.                                         for (i=1;i<=l;i++) a[offset+i].val=s[i];
     
146.                                         int tm=offset+Build(1,l);
     
147.                                         int L=Getkth(root,curpos+1); ///这个偏移要注意 光标位置0 就把一号假节点转到根
     
148.                                         int R=Getkth(root,curpos+2);
     
149.                                         Splay(L,root),Splay(R,a[root].s[1]);
     
150.                                         a[R].s[0]=tm,a[tm].fa=R;
     
151.                                         pushup(R),pushup(L);
     
152.                                 }
     
153.                         if (opt[0]=='G')
     
154.                                 {
     
155.                                         int k;
     
156.                                         scanf("%d",&k);
     
157.                                         int L=Getkth(root,curpos+1);
     
158.                                         int R=Getkth(root,curpos+k+2);
     
159.                                         Splay(L,root),Splay(R,a[root].s[1]);
     
160.                                         BSTPr(a[R].s[0]);
     
161.                                         printf("\n");
     
162.                                 }
     
163.                         if (opt[0]=='D')
     
164.                                 {
     
165.                                         int k;
     
166.                                         scanf("%d",&k);
     
167.                                         int L=Getkth(root,curpos+1);
     
168.                                         int R=Getkth(root,curpos+k+2);
     
169.                                         Splay(L,root),Splay(R,a[root].s[1]);
     
170.                                         a[R].s[0]=0;
     
171.                                         pushup(R),pushup(L);
     
172.                                 }
     
173.                         if (opt[0]=='P') curpos--;
     
174.                         if (opt[0]=='N') curpos++;
     
175.                         ///BSTPr(root);cout<<endl;
     
176.                 }
     
177.         return 0;
     
178. }
     
179. /*
     
180. 10
     
181. Insert 10
     
182. abcdefghij
     
183. Move 5
     
184. Insert 10
     
185. 0123456789
     
186. Move 3
     
187. Ins 2
     
188. **
     
189. Move 10
     
190. In 3
     
191. %%%
     
192. Del 3
     
193. 
     
194. 
     
195. */

复制代码