「BZOJ1552 / 3506」[Cerc2007] robotic sort

2014年9月10日6,0742

Description

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]反转(单个物品)。

Sample Input

6
3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

题解

由于我比较逗，所以写法的常数也很大T T

就是用splay维护序列的最小值位置以及实现翻转

找到最小值的节点，转到根，它左子树的结点个数+1就是它在序列中的位置

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,root,top;
int ans[100005],s[100005];
int fa[100005],c[100005][2];
int v[100005],mn[100005],size[100005],pos[100005];
bool rev[100005];
struct data{int pos,v;}a[100005];
inline bool operator<(data a,data b){return a.pos<b.pos;}
inline bool cmp(data a,data b){return a.v<b.v||(a.v==b.v&&a.pos<b.pos);}
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	mn[x]=v[x];pos[x]=x;
	if(mn[l]<mn[x]){mn[x]=mn[l];pos[x]=pos[l];}
	if(mn[r]<mn[x]){mn[x]=mn[r];pos[x]=pos[r];}
	size[x]=size[l]+size[r]+1;
}
void pushdown(int x)
{
    int l=c[x][0],r=c[x][1];
	rev[x]^=1;rev[l]^=1;rev[r]^=1;
	swap(c[x][0],c[x][1]);
}
void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l,r;
    if(c[y][0]==x)l=0;else l=1;r=l^1;
    if(y==k)k=x;
    else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
    c[y][l]=c[x][r];c[x][r]=y;
    update(y);update(x);
}
void splay(int x,int &k)
{
	top=0;s[++top]=x;
    for(int i=x;fa[i];i=fa[i])
        s[++top]=fa[i];
    for(int i=top;i;i--)
        if(rev[s[i]])pushdown(s[i]);
    while(x!=k)
    {
        int y=fa[x],z=fa[y];
        if(y!=k)
        {    
            if(c[y][0]==x^c[z][0]==y)
                rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}
int find(int x,int rk)
{
	if(rev[x])pushdown(x);
	int l=c[x][0],r=c[x][1];
	if(size[l]+1==rk)return x;
	else if(size[l]>=rk)return find(l,rk);
	else return find(r,rk-size[l]-1);
}
int querymn(int L,int R)
{
	int x=find(root,L),y=find(root,R+2);
	splay(x,root);splay(y,c[x][1]);
	int z=c[y][0];
	return pos[z];
}
void rever(int L,int R)
{
	int x=find(root,L),y=find(root,R+2);
	splay(x,root);splay(y,c[x][1]);
	int z=c[y][0];
	rev[z]^=1;
}
void build(int l,int r,int f)
{
	if(l>r)return;
	if(l==r)
	{
		fa[l]=f;size[l]=1;
		mn[l]=v[l]=a[l].v;pos[l]=l;
		if(l<f)c[f][0]=l;
		else c[f][1]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid-1,mid);build(mid+1,r,mid);
	fa[mid]=f;v[mid]=a[mid].v;update(mid);
	if(mid<f)c[f][0]=mid;
	else c[f][1]=mid;
}
int main()
{
    n=read();
    a[1].v=a[n+2].v=inf;mn[0]=inf;
	for(int i=2;i<=n+1;i++)
	{
		a[i].v=read();
		a[i].pos=i;
	}
	sort(a+2,a+n+2,cmp);
	for(int i=2;i<=n+1;i++)a[i].v=i-1;
	sort(a+2,a+n+2);
	build(1,n+2,0);
	root=(n+3)>>1;
	for(int i=1;i<=n;i++)
	{
		int x=querymn(i,n);
		splay(x,root);
		ans[i]=size[c[x][0]];
		rever(i,ans[i]);
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d",ans[i]);
		if(i!=n)printf(" ");
	}
	return 0;
}

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define pa pair<int,int>

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,root,top;

int ans[100005],s[100005];

int fa[100005],c[100005][2];

int v[100005],mn[100005],size[100005],pos[100005];

bool rev[100005];

struct data{int pos,v;}a[100005];

inline bool operator<(data a,data b){return a.pos<b.pos;}

inline bool cmp(data a,data b){return a.v<b.v||(a.v==b.v&&a.pos<b.pos);}

void update(int x)

{

int l=c[x][0],r=c[x][1];

mn[x]=v[x];pos[x]=x;

if(mn[l]<mn[x]){mn[x]=mn[l];pos[x]=pos[l];}

if(mn[r]<mn[x]){mn[x]=mn[r];pos[x]=pos[r];}

size[x]=size[l]+size[r]+1;

}

void pushdown(int x)

{

int l=c[x][0],r=c[x][1];

rev[x]^=1;rev[l]^=1;rev[r]^=1;

swap(c[x][0],c[x][1]);

}

void rotate(int x,int &k)

{

int y=fa[x],z=fa[y],l,r;

if(c[y][0]==x)l=0;else l=1;r=l^1;

if(y==k)k=x;

else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}

fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x,int &k)

{

top=0;s[++top]=x;

for(int i=x;fa[i];i=fa[i])

s[++top]=fa[i];

for(int i=top;i;i--)

if(rev[s[i]])pushdown(s[i]);

while(x!=k)

{

int y=fa[x],z=fa[y];

if(y!=k)

{

if(c[y][0]==x^c[z][0]==y)

rotate(x,k);

else rotate(y,k);

}

rotate(x,k);

}

int find(int x,int rk)

{

if(rev[x])pushdown(x);

int l=c[x][0],r=c[x][1];

if(size[l]+1==rk)return x;

else if(size[l]>=rk)return find(l,rk);

else return find(r,rk-size[l]-1);

}

int querymn(int L,int R)

{

int x=find(root,L),y=find(root,R+2);

splay(x,root);splay(y,c[x][1]);

int z=c[y][0];

return pos[z];

}

void rever(int L,int R)

{

int x=find(root,L),y=find(root,R+2);

splay(x,root);splay(y,c[x][1]);

int z=c[y][0];

rev[z]^=1;

}

void build(int l,int r,int f)

{

if(l>r)return;

if(l==r)

{

fa[l]=f;size[l]=1;

mn[l]=v[l]=a[l].v;pos[l]=l;

if(l<f)c[f][0]=l;

else c[f][1]=l;

return;

}

int mid=(l+r)>>1;

build(l,mid-1,mid);build(mid+1,r,mid);

fa[mid]=f;v[mid]=a[mid].v;update(mid);

if(mid<f)c[f][0]=mid;

else c[f][1]=mid;

}

int main()

{

n=read();

a[1].v=a[n+2].v=inf;mn[0]=inf;

for(int i=2;i<=n+1;i++)

{

a[i].v=read();

a[i].pos=i;

}

sort(a+2,a+n+2,cmp);

for(int i=2;i<=n+1;i++)a[i].v=i-1;

sort(a+2,a+n+2);

build(1,n+2,0);

root=(n+3)>>1;

for(int i=1;i<=n;i++)

{

int x=querymn(i,n);

splay(x,root);

ans[i]=size[c[x][0]];

rever(i,ans[i]);

}

for(int i=1;i<=n;i++)

{

printf("%d",ans[i]);

if(i!=n)printf(" ");

}

return 0;

}

« 「BZOJ1014」[JSOI2008] 火星人prefix 「CODEVS1743」反转卡片 »

debuggg

fa不吉利，应该用gen

hzwer

Fa乐器

hzwer.com _ Home | http://hzwer.com

「BZOJ1552 / 3506」[Cerc2007] robotic sort

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论