知识学习可参用 http://memphis.is-programmer.com/posts/46317.html
下面就说一些BZOJ（有一道POJ）上的习题
首先是基础的练习 1588、1208、1503
利用非旋转Treap的可快速合并和分裂的性质：1507
然后是一些关于区间操作之类的需要打标记：1269 1552（3506双倍经验）以及POJ的3580
还有一道综合很多操作的1500……
upd 4.6
1251 序列终结者
1861 书架
以上是高中时的学习记录……大概忘了差不多了。这几天突发奇想学点Treap解决一类嘿嘿嘿的问题。
我先大概复习了下以前写（抄）过的BZOJ的题：
1208 名次树的应用，用基本Treap的操作可解决。
3224 名次树各个操作的混杂。
1507 1269 都是文本编辑器类型的题。总之用Merge Split进行快速合并和分裂就对了 区间操作就是和线段树差不多 打标记。
1500 各种操作混杂 是锻炼Treap编码能力的好题 （打标记很多 我也不会 ） 以前问凌神要过代码……然而换了电脑给弄丢了。最近向R爷又要了一份QAQ。
好了下面说说我刚刚做的两道HDU的（模板）题（好难啊，其实是我菜）
http://acm.hdu.edu.cn/showproblem.php?pid=3487
hdu3487 题意：初始数列1-n 操作：1、CUT x y z 把x到y的数拿出来接到剩下数列的第z个数的后面。 2、FILP x y 把x到y的数翻转放回原位置。
总之……熟悉的话就是两个区间拆开和合并的过程 翻转就是模板类的。掏出模板东改西改，啊 过了！
hdu4453 题意：各种操作…… 懒得说了QAQ
也是区间合并分裂。注意最后两个操作 移动光标 因为本身是个圈。我们对圈没法很好的维护。我的想法就是把当前光标的数始终固定为第一个。那么Move 操作直接是把第一个接到最后面或
者最后一个接到最前面。这样就可以了。然后每次add和reverse都是前k1、k2个。所以不会涉及说超过尾部。那就可以做了。
下面贴个代码吧：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300010;
const int hzy=10007;
const int inf=(1<<30)-1;
typedef long long ll;
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)
int n,m;
char s[110];
int ans[maxn];
int tot;
struct Treap{
Treap *l,*r;
int size,fix,rdel;
int val;
Treap(int val_):fix(rand()),val(val_),size(1),l(NULL),r(NULL),rdel(0){}
inline void up(){
size=1+(l?l->size:0)+(r?r->size:0);
}
inline void down(){
if(rdel%2){
swap(l,r);
if(l) l->rdel+=rdel;
if(r) r->rdel+=rdel;
}
rdel=0;
}
}*root;
typedef pair<Treap*,Treap*> Droot;
inline int Size(Treap *x) {
return x?x->size:0;
}
void print(Treap *x)
{
x->down();
if(x->l) print(x->l);
//printf("%d ",x->val);
ans[++tot]=x->val;
if(x->r) print(x->r);
}
Treap *Merge(Treap *A,Treap *B)
{
if(!A) return B;
if(!B) return A;
A->down();B->down();
if(A->fix<B->fix)
{
A->r=Merge(A->r,B);
A->up();
return A;
}
else{
B->l=Merge(A,B->l);
B->up();
return B;
}
}
Droot Split(Treap *x,int k)
{
if(!x) return Droot(NULL,NULL);
x->down();
Droot y;
if(Size(x->l)>=k)
{
y=Split(x->l,k);
x->l=y.second;
x->up();
y.second=x;
}
else{
y=Split(x->r,k-Size(x->l)-1);
x->r=y.first;
x->up();
y.first=x;
}
return y;
}
Treap *Build(int n){
static Treap *stack[maxn],*x,*last;
int p=0;
rep(i,1,n){
x=new Treap(i);
last=NULL;
while(p && stack[p]->fix>x->fix){
stack[p]->up();
last=stack[p];
stack[p--]=NULL;
}
if(p) stack[p]->r=x;
x->l=last;
stack[++p]=x;
}
while(p) stack[p--]->up();
return stack[1];
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
if(n<0&&m<0) break;
root=Build(n);
memset(ans,0,sizeof(ans));
tot=0;
while(m--)
{
int u,v,w;
scanf("%s",s);
if(s[0]=='C') {
scanf("%d%d%d",&u,&v,&w);
Droot x=Split(root,u-1);
Droot y=Split(x.second,v-u+1);
Droot z=Split(Merge(x.first,y.second),w);
root=Merge(z.first,Merge(y.first,z.second));
}
else if(s[0]=='F') {
scanf("%d%d",&u,&v);
Droot x=Split(root,u-1);
Droot y=Split(x.second,v-u+1);
y.first->rdel++;
root=Merge(x.first,Merge(y.first,y.second));
}
}
print(root);
for(int i=1;i<=tot;i++)
if(i==1) printf("%d",ans[i]);
else printf(" %d",ans[i]);
puts("");
}
return 0;
}#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300010;
const int hzy=10007;
const int inf=(1<<30)-1;
typedef long long ll;
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)
int n,m,k1,k2;
char s[110];
int a[maxn];
int ans[maxn];
int tot;
struct Treap{
Treap *l,*r;
int size,fix,rdel,same;
int val;
Treap(int val_):fix(rand()),val(val_),size(1),l(NULL),r(NULL),rdel(0),same(0){}
inline void up(){
size=1+(l?l->size:0)+(r?r->size:0);
}
inline void down(){
if(rdel%2){
swap(l,r);
if(l) l->rdel+=rdel;
if(r) r->rdel+=rdel;
}
rdel=0;
if(same){
val+=same;
if(l) l->same+=same;
if(r) r->same+=same;
}
same=0;
}
}*root;
typedef pair<Treap*,Treap*> Droot;
inline int Size(Treap *x) {
return x?x->size:0;
}
void print(Treap *x)
{
x->down();
if(x->l) print(x->l);
printf("%d ",x->val);
//ans[++tot]=x->val;
if(x->r) print(x->r);
}
Treap *Merge(Treap *A,Treap *B)
{
if(!A) return B;
if(!B) return A;
A->down();B->down();
if(A->fix<B->fix)
{
A->r=Merge(A->r,B);
A->up();
return A;
}
else{
B->l=Merge(A,B->l);
B->up();
return B;
}
}
Droot Split(Treap *x,int k)
{
if(!x) return Droot(NULL,NULL);
x->down();
Droot y;
if(Size(x->l)>=k)
{
y=Split(x->l,k);
x->l=y.second;
x->up();
y.second=x;
}
else{
y=Split(x->r,k-Size(x->l)-1);
x->r=y.first;
x->up();
y.first=x;
}
return y;
}
Treap *Build(int* a){
static Treap *stack[maxn],*x,*last;
int p=0;
rep(i,1,n){
x=new Treap(a[i]);
last=NULL;
while(p && stack[p]->fix>x->fix){
stack[p]->up();
last=stack[p];
stack[p--]=NULL;
}
if(p) stack[p]->r=x;
x->l=last;
stack[++p]=x;
}
while(p) stack[p--]->up();
return stack[1];
}
void Insert(int k,int v)
{
Droot x=Split(root,k);
Treap *n=new Treap(v);
root=Merge(Merge(x.first,n),x.second);
}
void Same(int k,int L,int c)
{
Droot x=Split(root,k-1),y=Split(x.second,L);
y.first->same+=c;
root=Merge(Merge(x.first,y.first),y.second);
}
void Reverse(int L,int R)
{
Droot x=Split(root,L-1);
Droot y=Split(x.second,R-L+1);
y.first->rdel++;
root=Merge(x.first,Merge(y.first,y.second));
}
void Delete()
{
Droot x=Split(root,1);
root=x.second;
}
void MoveR()
{
Droot x=Split(root,1);
root=Merge(x.second,x.first);
}
void MoveL()
{
Droot x=Split(root,n-1);
root=Merge(x.second,x.first);
}
int main()
{
int Tcnt=0;
while(scanf("%d%d%d%d",&n,&m,&k1,&k2)==4&&n+m+k1+k2)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
root=Build(a);
//print(root);
printf("Case #%d:\n",++Tcnt);
while(m--)
{
scanf("%s",s);
int u,v,w;
if(s[0]=='q') {
Droot x=Split(root,1);
//puts("hh");
printf("%d\n",x.first->val);
root=Merge(x.first,x.second);
}
else if(s[0]=='m') {
scanf("%d",&u);
if(u==2) MoveR();
else MoveL();
}
else if(s[0]=='i') {
scanf("%d",&u);
Insert(1,u);
n++;
}
else if(s[0]=='r') {
Reverse(1,k1);
}
else if(s[0]=='d') {
Delete();
n--;
}
else if(s[0]=='a') {
scanf("%d",&u);
Same(1,k2,u);
}
}
}
return 0;
}
评论 (0)
