算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   对一个字符串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 西月弦 阅读(1553) 评论(1)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: uva 12583 可持久化treap
2013-03-24 09:58 | wuyiqi
好久没看你写题解,一来就是这么神的题。。。。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理