題目描述：
對一個字符串S(初始為空)，有Q次操作(Q<=50,000)，操作分三種：
1. 在某個位置p后面插入一個長度不大于100的字符串。
2. 刪除一段字符[l,r]
3. 輸出在第k次操作時，字符串(S_l ... S_r)
插入的字符不超過1,000,000個。
吐槽：
memory limit真是極限
算法分析：
支持任意區間的插入刪除，我們比較熟悉的是splay tree。可惜splay無法可持久化(至于為啥不知道 ><....)。
其次是塊鏈，空間和時間復雜度都是Q*sqrt(N)，難以接受。
其實支持這種操作的還有就是treap了，也是我唯一知道的可以可持久化的balanced tree。(AVL什么的也可以的哦，fanhq巨巨的blog有寫，可惜我不會)
treap可以在O(logn)的時間內split和merge，具體操作CLJ論文有寫。正好可以和插入一段/刪除一段對上，而且連rotate都不需要了。
這兩個操作可以保證heap的性質，也就同時能保證期望高度了。
注意逐個插入字符的時候還是要非持久化，否則空間是N*loglen + Q*logN的。而且要手動分配連續空間，否則都會MLE。
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<cassert>
6 using namespace std;
7 #define obfused
8 // treap
9 int flag = 0,ccnt = 0, memtop = 0;
10 struct node {
11 int key,sz,val;
12 char ch;
13 node *lc, *rc;
14 node(){lc = rc = NULL;}
15 void sumup(){
16 if(lc == NULL && rc == NULL) sz = 1;
17 else if(lc == NULL) sz = rc -> sz + 1;
18 else if(rc == NULL) sz = lc -> sz + 1;
19 else sz = rc -> sz + lc -> sz + 1;
20 }
21 node(char _c,int _key,int _val, node* _l,node *_r):
22 val(_val) ,lc(_l), rc(_r),ch(_c),key(_key){
23 ccnt++;
24 sumup();
25 }
26 node* mymerge(node*);
27 node* merge(node*);
28 void output(int);
29 pair<node*,node*> split(int);
30 void op();
31 void opc();
32 };
33 // memory pool
34 node mem[3000005];
35 node* mknode(char c,int key,int val,node* L,node *R){
36 mem[memtop] = node(c,key,val,L,R);
37 memtop++;
38 return &mem[memtop-1];
39 }
40 // build
41 const int N = 50005;
42 node *root[N];
43 char ch[105];
44 node* make(char *ch,int pos){
45 int n = strlen(ch);
46 node * ans = mknode(ch[0],rand(),pos,NULL,NULL);
47 for(int i = 1; i < n; i++){
48 node *tmp = mknode(ch[i],rand(),pos+i,NULL,NULL);
49 ans = ans -> mymerge(tmp);
50 }
51 return ans;
52 }
53 // treap's member function
54 node* node::mymerge(node *t){
55 if(t==NULL) return this;
56 if(key >= t->key){
57 if(rc == NULL)
58 rc = t;
59 else rc = rc -> mymerge(t);
60 sumup();
61 return this;
62 } else {
63 t -> lc = this;
64 t -> sumup();
65 return t;
66 }
67 }
68 node* node::merge(node *t){
69 if(t == NULL) return this;
70 if(key >= t-> key) {
71 if(rc == NULL) {
72 node *nd = mknode(ch,key,val,lc,t);
73 return nd;
74 } else {
75 node *nd = mknode(ch,key,val,lc,rc->merge(t));
76 }
77 } else {
78 if(t -> lc == NULL){
79 node *nd = mknode(t->ch,t->key,t->val,this,t->rc);
80 return nd;
81 } else {
82 node *nd = mknode(t->ch,t->key,t->val,merge(t->lc),t->rc);
83 }
84 }
85 }
86 pair<node*,node*> node:: split(int len){
87 // cout<<"split: "<<ch<<" "<<len<<endl;
88 pair<node*,node*> pr;
89 int cnt = 0;
90 if(lc != NULL) cnt = lc -> sz;
91 if(cnt >= len) {
92 if(lc == NULL) return make_pair((node*)NULL,this);
93 else {
94 pr = lc -> split(len);
95 node *L = pr.first;
96 node *R = mknode(ch,key,val,pr.second,rc);
97 return make_pair(L,R);
98 }
99 } else {
100 if(rc == NULL) return make_pair(this,(node*)NULL);
101 else {
102 pr = rc -> split(len -cnt - 1);
103 node *L = mknode(ch,key,val,lc,pr.first);
104 node *R = pr.second;
105 return make_pair(L,R);
106 }
107 }
108 }
109 void node:: output(int k){
110 int cnt = 0;
111 assert(k >=1 && k <= sz);
112 if(lc != NULL) cnt = lc -> sz;
113 if(k <= cnt) lc -> output(k);
114 else if(k == cnt + 1) {
115 printf("%c",ch);
116 if(ch == 'c') flag ++;
117 } else {
118 assert(rc != NULL);
119 rc -> output(k - cnt - 1);
120 }
121 }
122 void node:: op(){
123 cout<< ch <<" "<<val<<" "<<sz<<endl;
124 if(lc != NULL) cout<<"lc: "<<lc->ch<<endl;
125 if(rc != NULL) cout<<"rc: "<<rc->ch<<endl;
126 if(lc != NULL) lc->op();
127 if(rc != NULL) rc->op();
128 }
129 void node:: opc(){
130 if(lc != NULL) lc->opc();
131 cout<<ch;
132 if(rc != NULL) rc->opc();
133 }
134 // main && io
135 int main(){
136 int q,count = 0;
137 cin >> q;
138 for(int _=0;_<q;_++){
139 //cout<<"now: "<<_<<endl;
140 int cmd,pos,len,ver;
141 scanf("%d",&cmd);
142 if(cmd == 1) {
143 scanf("%d%s",&pos,ch);
144 #ifdef obfused
145 pos -= flag;
146 #endif
147 //cout<<pos<<" "<<ch<<endl;
148 node *t = make(ch,pos+1);
149 if(root[count] == NULL) {
150 root[++count] = t;
151 } else {
152 pair<node*,node*>pr = root[count]->split(pos);
153 t = t->merge(pr.second);
154 if(pr.first != NULL) t = pr.first->merge(t);
155 root[++count] = t;
156 }
157 } else if(cmd == 2){
158 scanf("%d%d",&pos,&len);
159 #ifdef obfused
160 pos -= flag,len -= flag;
161 #endif
162 // cout<<pos<<" "<<len<<endl;
163 pair<node*,node*>pr = root[count]->split(pos-1);
164 node* u = pr.first;
165 // if(u!=NULL){cout<<"u: "; u->op();u->opc(); cout<<endl;}
166 assert(pr.second != NULL);
167 pair<node*,node*>prn = pr.second-> split(len);
168 node* v = prn.second;
169 node* ans;
170 if(u == NULL) ans = v;
171 else ans = u->merge(v);
172 // if(v!=NULL){cout<<"v: "; v->op();v->opc(); cout<<endl;}
173 // ans -> opc(); cout<<endl;
174 root[++count] = ans;
175 // cout<<"count: "<<count<<endl;
176 } else {
177 scanf("%d%d%d",&ver,&pos,&len);
178 #ifdef obfused
179 pos -= flag, ver -= flag, len -= flag;
180 #endif
181 // cout<<ver<<" "<<pos<<" "<<len<<endl;
182 for(int i = 0; i < len; i++)
183 root[ver] -> output(pos + i);
184 printf("\n");
185 }
186 //root[count]->op();
187 // root[count]->opc();cout<<endl;
188 // cout<<ccnt<<endl;
189 }
190 }
191
posted on 2013-03-19 22:15
西月弦 閱讀(1584)
評論(1) 編輯 收藏 引用 所屬分類:
解題報告