Luogu U72177 火星人plus

Luogu U72177 火星人plus

解析

• 康托展开和逆康托展开的模板题
• 时间限制有点难受，线段树由于常数大过不了

Code

线段树(80分)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
inline LL read()
{
	LL z=0,b=1;char cs=getchar();
	while(cs<'0'||cs>'9'){if(cs=='-')b=-1;cs=getchar();}
	while(cs>='0'&&cs<='9'){z=z*10+cs-'0';cs=getchar();}
	return z*b;
}
inline void write(LL z)
{
	if(z<0) putchar('-'),z=-z;
	if(z>9) write(z/10);
	putchar(z%10+'0');
	return;
}
const int N=1e5+5;
LL n,m,a[N];
struct Tree
{
	LL tr[N<<2];
	void pushup(int root)
	{
		tr[root]=tr[root*2]+tr[root*2+1];
		return;
	}
	void build(int root,int l,int r)
	{
		if(l==r)
		{
			tr[root]=1;
			return;
		}
		int mid=(l+r)>>1;
		build(root*2,l,mid);
		build(root*2+1,mid+1,r);
		pushup(root);
		return;
	}
	void update(int root,int l,int r,LL u,LL v)
	{
		if(l==r)
		{
			tr[root]=v;
			return;
		}
		int mid=(l+r)>>1;
		if(mid>=u) update(root*2,l,mid,u,v);
		else update(root*2+1,mid+1,r,u,v);
		pushup(root);
		return;
	}
	LL query(int root,int l,int r,LL ll,LL rr)
	{
		if(l==ll&&r==rr) return tr[root];
		int mid=(l+r)>>1;
		if(mid>=rr) return query(root*2,l,mid,ll,rr);
		else
		{
			if(mid<ll) return query(root*2+1,mid+1,r,ll,rr);
			else return query(root*2,l,mid,ll,mid)+query(root*2+1,mid+1,r,mid+1,rr);
		}
	}
}str;
LL deal(LL v)
{
	LL l=1,r=n;
	while(l<r)
	{
		LL mid=(l+r)>>1;
		if(str.query(1,1,n,1,mid)-1<v) l=mid+1;
		else r=mid;
	}
	str.update(1,1,n,l,0);
	return l;
}
int main()
{
	n=read(),m=read();
	str.build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		str.update(1,1,n,a[i],0);
		a[i]=str.query(1,1,n,1,a[i]);
	}
	a[n]+=m;
	for(int i=n;i>=1;i--)
	{
		a[i-1]+=a[i]/(n-i+1);
		a[i]%=n-i+1;
	}
	str.build(1,1,n);
	for(int i=1;i<=n;i++) write(deal(a[i])),putchar(' ');
	putchar('
');
	return 0;
}

树状数组(100分)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
inline LL read()
{
	LL z=0,b=1;char cs=getchar();
	while(cs<'0'||cs>'9'){if(cs=='-')b=-1;cs=getchar();}
	while(cs>='0'&&cs<='9'){z=z*10+cs-'0';cs=getchar();}
	return z*b;
}
inline void write(LL z)
{
	if(z<0) putchar('-'),z=-z;
	if(z>9) write(z/10);
	putchar(z%10+'0');
	return;
}
const int N=1e5+5;
LL n,m,a[N],ctr[N];
LL lowbit(LL u)
{
	return u&(-u);
}
void update(LL u,LL v)
{
	for(;u<=n;u+=lowbit(u)) ctr[u]+=v;
	return;
}
LL query(LL u)
{
	LL res=0;
	for(;u;u-=lowbit(u)) res+=ctr[u];
	return res;
}
LL deal(LL v)
{
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(query(mid)-1<v) l=mid+1;
		else r=mid;
	}
	update(l,-1);
	return l;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) update(i,1);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		update(a[i],-1);
		a[i]=query(a[i]);
	}
	a[n]+=m;
	for(int i=n;i>=1;i--)
	{
		a[i-1]+=a[i]/(n-i+1);
		a[i]%=n-i+1;
	}
	for(int i=1;i<=n;i++) update(i,1);
	for(int i=1;i<=n;i++) write(deal(a[i])),putchar(' ');
	putchar('
');
	return 0;
}