NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2014高中組決賽
 NPSC2014 高中組決賽 D. 蚯蚯(扭)

作者 主題: NPSC2014 高中組決賽 D. 蚯蚯(扭)  (閱讀 1596 次)

jacky860226

  • 新手
  • *
  • 文章數: 3
    • 檢視個人資料
NPSC2014 高中組決賽 D. 蚯蚯(扭)
« 於: 二月 11, 2015, 04:33:58 pm »

這題是考持久化隨機二叉樹(Randomized Binary Search Tree)的應用
這邊提供兩種做法

1、無懶惰標記
用一正一反兩顆RBST維護區間,要反轉就拔出來交換兩顆子樹
zerojudge AC 1.4s有點慢

這邊使用了引用計數
做記憶體回收

代碼: [選擇]
#include<bits/stdc++.h>
using namespace std;
#ifndef REFERENCE_POINTER
#define REFERENCE_POINTER
template<typename T>
struct _RefCounter{
T data;
int ref;
_RefCounter(const T&d=0):data(d),ref(0){}
};
template<typename T>
struct reference_pointer{
_RefCounter<T> *p;
T *operator->(){
return &(*p).data;
}
T &operator*(){
return p->data;
}
operator int(){return(int)(long long)p;}
reference_pointer&operator=(const reference_pointer &t){
if(p&&--(*p).ref==0)delete p;
p=t.p;
p&&(*p).ref++;
return*this;
}
reference_pointer(_RefCounter<T> *t=0):p(t){
p&&(*p).ref++;
}
reference_pointer(const reference_pointer &t):p(t.p){
p&&(*p).ref++;
}
~reference_pointer(){
if(p&&--(*p).ref==0)delete p;
}
};
template<typename T,typename... _Args>
inline reference_pointer<T>
new_reference(_Args... __args){
return reference_pointer<T>
(new _RefCounter<T>(T(__args...)));
}
#endif
struct node;
typedef reference_pointer<node> pt;
struct node{
char data;
int size;
pt l,r;
node(const node&t):data(t.data),size(t.size),l(t.l),r(t.r){}
node(const char &d){
size=1;
data=d;
}
inline void up(){
size=1;
if(l)size+=l->size;
if(r)size+=r->size;
}
};
inline int size(pt &o){return o?o->size:0;}
void split(pt o,pt &a,pt &b,const int &k){
if(!o)a=b=NULL;
else{
o=new_reference<node>(*o);
if(k<=size(o->l)){
b=o;
split(o->l,a,b->l,k);
}else{
a=o;
split(o->r,a->r,b,k-size(o->l)-1);
}
o->up();
}
}
pt merge(pt a,pt b){
if(!a||!b)return a?a:b;
static int x;
if(x++%(a->size+b->size)<a->size){
a=new_reference<node>(*a);
a->r=merge(a->r,b);
a->up();
return a;
}else{
b=new_reference<node>(*b);
b->l=merge(a,b->l);
b->up();
return b;
}
}
pt build(char *s,int l,int r){
int mid=(l+r)>>1;
pt k=new_reference<node>(s[mid]);
if(l<=mid-1)k->l=build(s,l,mid-1);
if(mid+1<=r)k->r=build(s,mid+1,r);
k->up();
return k;
}
void dfs(pt&t){
if(!t)return;
dfs(t->l);
putchar(t->data);
dfs(t->r);
}
char s[50005];
pt root,root2;
pt a,b,c,d,e,f,g,h;
int n,m,t;
int l,r,x;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
scanf("%s",s);
root=build(s,0,n-1);
reverse(s,s+n);
root2=build(s,0,n-1);
while(m--){
scanf("%d%d%d",&x,&l,&r);
if(x==1){
split(root,a,b,l-1);
split(b,c,d,r-l+1);
dfs(c);puts("");
}else if(x==2){
split(root,a,b,l-1);
split(b,c,d,r-l+1);
root=merge(merge(a,merge(c,c)),d);
int rr=n-l+1;
int ll=n-r+1;
n+=r-l+1;
split(root2,a,b,ll-1);
split(b,c,d,rr-ll+1);
root2=merge(merge(a,merge(c,c)),d);
}else{
split(root,a,b,l-1);
split(b,c,d,r-l+1);

int rr=n-l+1;
int ll=n-r+1;
split(root2,e,f,ll-1);
split(f,g,h,rr-ll+1);

root2=merge(merge(e,c),h);
root=merge(merge(a,g),d);
}
}
}
return 0;
}

2、懶惰標計

使用懶惰標計進行下推,要特別注意要複製哪些節點
zerojudge AC 0.4s 跟標程一樣快

代碼: [選擇]
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int s;
bool rev;
char c;
node(char d):l(0),r(0),s(1),rev(0),c(d){}
node(node &p):l(p.l),r(p.r),s(p.s),rev(p.rev),c(p.c){}
inline void up(){
s=1+(l?l->s:0)+(r?r->s:0);
}
inline void down(){
if(!rev)return;
swap(l,r);
if(l){
l=new node(*l);
l->rev^=1;
}
if(r){
r=new node(*r);
r->rev^=1;
}
rev=0;
}
};
inline int ran(){
static int x=20150211;
return x=(x*0xdefaced+1)&INT_MAX;
}
node *merge(node *a,node *b){
if(!a||!b)return a?a:b;
if(ran()%(a->s+b->s)<a->s){
a=new node(*a);
a->down();
a->r=merge(a->r,b);
a->up();
return a;
}else{
b=new node(*b);
b->down();
b->l=merge(a,b->l);
b->up();
return b;
}
}
int size(node *o){return o?o->s:0;}
void split(node *o,node *&a,node *&b,int k){
if(!o)a=b=0;
else{
o=new node(*o);
o->down();
if(k<=size(o->l)){
b=o;
split(o->l,a,b->l,k);
}else{
a=o;
split(o->r,a->r,b,k-size(o->l)-1);
}
o->up();
}
}
void dfs(node *p,bool rev){
if(!p)return;
rev^=p->rev;
if(rev){
dfs(p->r,rev);
putchar(p->c);
dfs(p->l,rev);
}else{
dfs(p->l,rev);
putchar(p->c);
dfs(p->r,rev);
}
}
node *build(char *s,int l,int r){
int mid=(l+r)>>1;
node *p=new node(s[mid]);
if(l<=mid-1)p->l=build(s,l,mid-1);
if(mid+1<=r)p->r=build(s,mid+1,r);
p->up();
return p;
}
int t,n,m;
int e,l,r;
char s[50005];
node *root,*a,*b,*c,*d;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%s",&n,&m,s);
root=build(s,0,n-1);
while(m--){
scanf("%d%d%d",&e,&l,&r);
split(root,a,b,l-1);
split(b,c,d,r-l+1);
if(e==1){
dfs(c,0);puts("");
}else if(e==2){
root=merge(a,merge(c,b));
}else{
c->rev^=1;
root=merge(a,merge(c,d));
}
}
}
return 0;
}

如果有不清楚的地方,歡迎來日月卦長的模板庫,這裡有各種平衡樹及資料結構
日月卦長的模板庫http://sunmoon-template.blogspot.tw/
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2014高中組決賽
 NPSC2014 高中組決賽 D. 蚯蚯(扭)