注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3678]Wangxz与OJ  

2014-08-22 20:42:03|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个题有一个故事。。
这本来是Lizitong神犇出的Splay模板题,然后裸Splay、块链、rope各种轻松过
然后Claris神犇看了这道题:”Splay缩点?“
我:”不缩点好像也能过“
Claris神犇:”啥?“
然后他就加♂强了数据2333
然后大家都被艹翻了【25人斩】
然后我就乖乖写了缩点Splay
一开始各种手残+脑残调了半天。。
后来好不容易拍不出错了
交上去TLE?!
最后发现是内存池写挂了
速度Rank1码长Rank1这真是喜闻乐见

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 20000+10;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
int data[N],all;
struct Node{
Node();
int l,r,size;
Node *ch[2],*fa;
void count(){size = ch[0]->size+ch[1]->size+(r-l+1);}
short pl(){return this==fa->ch[0]?0:1;}
}*null,house[N];
Node::Node(){ch[0]=ch[1]=fa=null;l=r=0;size=1;}
int hn;queue<Node*>pupa;
Node *newNode(){
if(hn<N){house[hn]=Node();return &house[hn++];}
if(pupa.empty())return new Node();
Node *now= pupa.front();pupa.pop();
*now = Node();
return now;
}
void print(Node *ro,int deep=0){
for(int i=1;i<=deep;i++)printf(" ");
printf("%d %d %d\n",ro->l,ro->r,ro->size);
for(int i=1;i<=deep;i++)printf(" ");
printf("ch[0]:\n");
if(ro->ch[0]!=null)print(ro->ch[0],deep+1);else printf("\n");
for(int i=1;i<=deep;i++)printf(" ");
printf("ch[1]:\n");
if(ro->ch[1]!=null)print(ro->ch[1],deep+1);else printf("\n");
}
void del(Node *&r){pupa.push(r);r=null;}
int n,m;
class Splay{
private:
Node *Build(int l,int r){
if(r<l) return null;
Node *ro = newNode();
int mid=(l+r)/2;
if(l<r){
ro->ch[0] = Build(l,mid-1);
ro->ch[1] = Build(mid+1,r);
if(ro->ch[0]!=null)ro->ch[0]->fa=ro;
if(ro->ch[1]!=null)ro->ch[1]->fa=ro;
}ro->l=ro->r = data[mid];
ro->count();
return ro;
}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==null) return;
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
if(r->fa!=null)r->fa->ch[r->pl()] = k;
else ROOT= k ;
k->fa = r->fa;r->fa = k;
k->ch[x]=r;
r->count();k->count();
}
void splay(Node *r,Node *tar = null){
for(;r->fa!=tar;rotate(r))
if(r->fa->fa!=tar)
rotate(r->pl()==r->fa->pl()?r->fa:r);
}
void cut(Node *r,int k){//l~k|k+1~r
Node *l = newNode();
l->l = k+1;l->r = r->r;
r->r=k;
l->ch[0]=null;l->ch[1]=r->ch[1];l->fa=r;
r->ch[1] = l;l->ch[1]->fa = l;
l->count(); r->count();
//splay
}
void pack(int l,int r){
int a;
Node *ro = kth(ROOT,l);
a=l-all-ro->ch[0]->size-1 + ro->l;
if(a+1 <= ro->r)cut(ro,a);
splay(ro);

ro = kth(ROOT,r);
a=r-all-ro->ch[0]->size-1 + ro->l;a-=1;
if(a>=ro->l){cut(ro,a);ro=ro->ch[1];}
splay(ro,ROOT);
ROOT->count();
}
void remove(Node *&r){
if(r->ch[0]!=null)remove(r->ch[0]);
if(r->ch[1]!=null)remove(r->ch[1]);
del(r);
}
public:
Node *ROOT;
void preset(){
null=newNode();
null->ch[0]=null->ch[1]=null->fa = null;
null->size=0;
ROOT = newNode();
ROOT->ch[1]=newNode();
ROOT->ch[1]->fa=ROOT;
ROOT->ch[1]->ch[0] = Build(1,n);
ROOT->ch[1]->ch[0]->fa=ROOT->ch[1];
ROOT->ch[1]->count();
ROOT->count();
}
Node *kth(Node *r,int k){
all=0;
while(r!=null){
if(k<=r->ch[0]->size) r=r->ch[0];
else if(k<=r->size-r->ch[1]->size) return r;
else all+=r->size-r->ch[1]->size,k-=r->size-r->ch[1]->size,r=r->ch[1];
}return r;
}
void Insert(int pos,int l,int r){
pack(pos,pos+1);
Node *& ro = ROOT->ch[1]->ch[0];
ro= new Node();
ro->fa = ROOT->ch[1];
ro->l = l;ro->r = r;
ro->count();
ROOT->ch[1]->count();
ROOT->count();
}
void Delete(int l,int r){
pack(l-1,r+1);
remove(ROOT->ch[1]->ch[0]);
ROOT->ch[1]->count();
ROOT->count();
}
}tree;
int main(){
int i,j,a,b,c;
n=scan();m=scan();
for(i=1;i<=n;i++)data[i]=scan();
tree.preset();
for(j=1;j<=m;j++){
a=scan();
if(a==0){//insert
c=scan();a=scan();b=scan();
tree.Insert(c+1,a,b);
}else if(a==1){//delete
a=scan();b=scan();
tree.Delete(a+1,b+1);
}else if(a==2){//ask
a=scan();
Node *r =tree.kth(tree.ROOT,a+1);
printf("%d\n",a+1-all-r->ch[0]->size-1+r->l);
}
}
return 0;
}

题解:
缩点Splay
因为是连续的所以每次只插入一个点,需要的时候割开
  评论这张
 
阅读(88)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017