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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3506][Cqoi2014]排序机械臂  

2015-01-15 22:07:40|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3506: [Cqoi2014]排序机械臂

题意被略掉了……1552又是个权限题,所以贴一下题面:
[BZOJ3506][Cqoi2014]排序机械臂 - 时光机 - 时光机TimeMachine

Input
输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000。第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号。
Output
输出共一行,N个用空格隔开的正整数P1,P2,P3…Pn,(1 < = Pi < = N),Pi表示第i次操作前第i小的物品所在的位置。 注意:如果第i次操作前,第i小的物品己经在正确的位置Pi上,我们将区间[Pi,Pi]反转(单个物品)。

输出的最后一个数字后不要加空格,否则会PE

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E5+100;
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 n,m,data[N],list[N];
struct Node{
Node();
int size;short rev;
Node *ch[2],*fa;
void count();void push();void setf();
bool pl(){return this==fa->ch[1];}
}*null,point[N];
void Node::setf(){if(ch[0]!=null)ch[0]->fa=this;if(ch[1]!=null)ch[1]->fa=this;}
void Node::count(){if(this==null)return;size = ch[0]->size + ch[1]->size + 1;}
void Node::push(){
if(this==null)return;
if(rev){
swap(ch[0],ch[1]);
ch[0]->rev^=1;
ch[1]->rev^=1;
rev=0;
}
}
Node::Node(){ch[0]=ch[1]=fa=null;size=rev=0;}
struct Splay{
Node *ROOT;
Splay(){
if(!null){
null = new Node;
*null = Node();
null->size = 0;
}
}
void rotate(Node *k){
Node *r = k->fa;if(k==null||r==null)return;
r->push();k->push();
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);
r->push();
}
Node *build(Node *father=null,int l=1,int r=n){
if(l>r)return null;
int mid = (l+r)/2;
point[data[mid]] = Node();
Node *re = &point[data[mid]];
re->fa = father;
re->ch[0] = build(re,l,mid-1);
re->ch[1] = build(re,mid+1,r);
re->count();return re;
}
void preset(){
ROOT = build();
}
int rank(int i){splay(&point[i]);return ROOT->ch[0]->size+1;}
void reverse(int l,int r){//point[l] point[r]
if(l==r)return;
Node *lr=&point[l],*rr=&point[r];
splay(lr);splay(rr,ROOT);
//strange swap..
swap(lr->ch[0],rr->ch[0]);
lr->ch[1] = rr->ch[1];rr->ch[1] = lr;
rr->fa = null;lr->fa = rr;
lr->setf();rr->setf();
lr->count();rr->count();//*
ROOT = rr;
ROOT->ch[1]->ch[0]->rev^=1;
}
Node *kth(int k){
Node *r = ROOT;//k++;
while(r!=null){
r->push();
if(k<=r->ch[0]->size)r = r->ch[0];
else if(k<=r->ch[0]->size+1)return r;
else k-=r->ch[0]->size+1,r=r->ch[1];
}return null;
}
void print(Node *r,int d=0){
if(r==null)return;r->push();
for(int i=1;i<=d;i++)printf(" ");
printf("(%d) %d {\n",r-point,r->size);
for(int i=1;i<=d;i++)printf(" ");printf("ch[0]:\n");
print(r->ch[0],d+1);
for(int i=1;i<=d;i++)printf(" ");printf("ch[1]:\n");
print(r->ch[1],d+1);
for(int i=1;i<=d;i++)printf(" ");printf("}\n");
}
void print(){print(ROOT);}
void pint(Node *r,int d=0){
if(r==null)return;
r->push();
pint(r->ch[0],d+1);
//printf("%d ",r-point);
//if(d > fuck)fuck = d;
list[++list[0]] = r-point;
pint(r->ch[1],d+1);
}
void pint(){list[0]=0;pint(ROOT);printf("\n");}
}st;
typedef pair<int,int> Data;
Data cpy[N];
bool dacmp(Data a,Data b){return a.first==b.first?a.second<b.second:a.first<b.first;}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++){
data[i] = scan();
cpy[i] = Data(data[i],i);
}
sort(cpy+1,cpy+1+n,dacmp);
for(i=1;i<=n;i++)data[cpy[i].second] = i;
st.preset();
for(i=1;i<=n;i++){
a = st.kth(i)-point;
b=i;
printf("%d%s",st.rank(b),i==n?"":" ");
//printf("[%d, %d]",a,b);
st.reverse(a,b);
//printf("### Operation %d ###\n",i);st.pint();
}
return 0;
}

题解:
用Splay模拟……没啥好说的
认真读题……题目里说输入的n个数,不仅随意而且可能有重复
比较神奇的是我一开始size维护错了居然依旧AC= =、
然后还发现按照题目里的顺序进行操作会导致左半边退化成链……这个一定要小心(虽然这个题无所谓
这个题我的reverse姿势比较奇怪……退化和这个有关?
  评论这张
 
阅读(61)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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