uva12538 Version Controlled IDE

发表于 | 更新于

Link

uva太慢了，还是再vjudge上看题目吧。。

FHQ Treap

学习了FHQ Treap的基本操作，以及可持久化Treap的写法。

Merge(a,b)

把a，b合并为一个Treap。前提是a中的所有元素都比b中的小，这样就可以按照可并堆的方法合并了。

Split(pos,K)

将treap分裂成两个，第一个包含了前K个元素，第二个包含剩下的元素。写法和平衡树的查找第K大有些类似。 函数返回一个pair，具体实现比较容易脑补出来。

Build(seq)

把一个序列O(n)O(n)构建成Treap。 如果是其它的平衡树的话，插入一个序列一般是用递归建立一个完全二叉树。Treap并不能那么做，因为以节点的优先级来确保全局的平衡。 于是Orz Sengxian。 对于一个有序的序列，依次处理每个元素。 维护一个栈，为每个元素新建一个节点，如果新的节点的优先级比栈顶元素小，就退栈，相应地连边。

Persistence

在Merge和Split中，对节点的所有修改都要在副本上进行。每次的花费空间期望应该是O(log n)O(log\ n)级别的。但是由于一次操作可能要多次Split和Merge，导致空间常数大了一些。。如果大神们有又好写又省空间的写法欢迎指教。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define sred(x) scanf("%s",x+1)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXL=10000000+10,MAXN=50000+10,P=1e5+7;
using std::pair;
using std::make_pair;
struct TreapNode
{
	TreapNode *son[2];
	char c;int py,sz;
	TreapNode(){}
	TreapNode(int _py):py(_py){son[0]=son[1]=0;}
	void up(){sz=son[0]->sz+son[1]->sz+1;}
}*null=new TreapNode,*root[MAXN],*ME=new TreapNode[MAXL];
typedef pair<TreapNode*,TreapNode*> Np;
void InitTreap()
{
	null->py=P,null->sz=null->c=0;
	null->son[0]=null->son[1]=null;
}
TreapNode *newTreapNode(char c)
{
	static TreapNode *cur;
	cur=ME++;cur->c=c;cur->py=rand()%P;
	cur->son[0]=cur->son[1]=null;
	return cur;
}
TreapNode *newTreapNode(TreapNode *old)
{
	static TreapNode *cur;
	cur=ME++;*cur=*old;return cur;
}
TreapNode *Build(char *s)
{
	static TreapNode *stack[MAXN],*empty=new TreapNode(-P);
	static int top;stack[top=0]=empty;
	for(int i=1,endi=strlen(s+1);i<=endi;i++)
	{
		TreapNode *cur=newTreapNode(s[i]),*last=null;
		while(cur->py<stack[top]->py)
		{
			stack[top]->up();//其形态已经确定了
			last=stack[top--];
		}
		stack[top]->son[1]=cur;cur->son[0]=last;
		stack[++top]=cur;
	}
	while(top)
	{
		stack[top-1]->son[1]=stack[top];
		stack[top]->up();top--;
	}
	return empty->son[1];
}
TreapNode *Merge(TreapNode *a,TreapNode *b)
{
	if(a==null) return newTreapNode(b);
	if(b==null) return newTreapNode(a);
	TreapNode *cur;
	if(a->py<=b->py)
	{
		cur=newTreapNode(a);
		cur->son[1]=Merge(cur->son[1],b);
		cur->up();
	}
	else
	{
		cur=newTreapNode(b);
		cur->son[0]=Merge(a,cur->son[0]);
		cur->up();
	}
	return cur;
}
Np Split(TreapNode *&pos,int K)
{
	Np res=make_pair(null,null);
	if(pos==null) return res;
	pos=newTreapNode(pos);
	if(K<=pos->son[0]->sz)
	{
		res=Split(pos->son[0],K);
		pos->son[0]=res.second,pos->up();
		res.second=pos;
	}
	else
	{
		res=Split(pos->son[1],K-pos->son[0]->sz-1);
		pos->son[1]=res.first,pos->up();
		res.first=pos;
	}
	return res;
}
TreapNode *Insert(TreapNode *root,int p,char *s)
{
	TreapNode *nodes=Build(s);
	Np sp=Split(root,p);
	return Merge(Merge(sp.first,nodes),sp.second);
}
TreapNode *Delete(TreapNode *root,int p,int cnt)//从p开始的cnt个
{
	--p;
	Np sp1=Split(root,p),
	   sp2=Split(sp1.second,cnt);
	return Merge(sp1.first,sp2.second);
}
int d;
void out(TreapNode *pos)
{
	if(pos==null) return;
	out(pos->son[0]);
	putchar(pos->c);
	if(pos->c=='c') d--;	
	out(pos->son[1]);
}
void PutStr(TreapNode *root,int p,int cnt)
{
	--p;
	Np sp1=Split(root,p),
	   sp2=Split(sp1.second,cnt);
	out(sp2.first);puts("");
}
void print(TreapNode *root)
{
	puts("BEGIN");
	out(root);
	puts("\nEND");
}
int main()
{
	srand(0x1f1f1f1f);
	InitTreap();
	static char s[MAXN];
	int n,ver;red(n);
	root[ver=0]=null;
	for(int i=1;i<=n;i++)
	{
		int opt,v,p,c;red(opt);
		switch(opt)
		{
			case 1:red(p),sred(s);p+=d;
				   root[ver+1]=Insert(root[ver],p,s);
				   ver++;
				   break;
			case 2:red(p),red(c);p+=d,c+=d;
				   root[ver+1]=Delete(root[ver],p,c);
				   ver++;
				   break;
			case 3:red(v),red(p),red(c);v+=d,p+=d,c+=d;
				   PutStr(root[v],p,c);
				   break;
		}
		//print(root[ver]);
	}
	return 0;
}