[BZOJ5249][九省联考2018]IIIDX：线段树+贪心

分析

GXZlegend orz

构造出一组合法的解并不是难事，但是我们需要输出的是字典序最大的解。

字典序最大有另一种理解方式，就是让越小的数尽量越靠后。

我们从树的根结点出发，从1开始填数，构造出来的一定是一组合法的解。

对于每种相同的数，可以通过线段树上二分逐个确定他们的最优位置，具体细节可以看代码。

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

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

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=500005;

int n,d[MAXN];

int ecnt,head[MAXN],siz[MAXN],ans[MAXN];

double k;

int sum[MAXN<<2],loc,ql,qr,kk;

struct Edge{

	int to,nxt;

}e[MAXN<<1];

inline void add_edge(int bg,int ed){

	++ecnt;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

#define mid ((l+r)>>1)

#define lc (o<<1)

#define rc ((o<<1)|1)

void upd(int o,int l,int r){

	if(l==r){

		sum[o]+=kk;

		return;

	}

	if(loc<=mid) upd(lc,l,mid);

	else upd(rc,mid+1,r);

	sum[o]=sum[lc]+sum[rc];

}

int query(int o,int l,int r){

	if(l==r) return l;

	if(sum[rc]>=kk) return query(rc,mid+1,r);

	else return kk-=sum[rc],query(lc,l,mid);

}

#undef mid

#undef lc

#undef rc

int main(){

	n=read();

	scanf("%lf",&k);

	rin(i,1,n) d[i]=read(),siz[i]=1;

	std::sort(d+1,d+n+1);

	rin(i,1,n) add_edge((int)floor(i/k),i);

	irin(i,n,1) siz[(int)floor(i/k)]+=siz[i];

	trav(i,0){int ver=e[i].to;loc=ver,kk=siz[ver];upd(1,1,n);}

	int cnt=1;

	rin(i,2,n+1){

		if(d[i]==d[i-1]){#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

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

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=500005;

int n,d[MAXN];

int ecnt,head[MAXN],siz[MAXN],ans[MAXN];

double k;

int sum[MAXN<<2],loc,ql,qr,kk;

struct Edge{

	int to,nxt;

}e[MAXN<<1];

inline void add_edge(int bg,int ed){

	++ecnt;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

#define mid ((l+r)>>1)

#define lc (o<<1)

#define rc ((o<<1)|1)

void upd(int o,int l,int r){

	if(l==r){

		sum[o]+=kk;

		return;

	}

	if(loc<=mid) upd(lc,l,mid);

	else upd(rc,mid+1,r);

	sum[o]=sum[lc]+sum[rc];

}

int query(int o,int l,int r){

	if(l==r) return l;

	if(sum[rc]>=kk) return query(rc,mid+1,r);

	else return kk-=sum[rc],query(lc,l,mid);

}

#undef mid

#undef lc

#undef rc

int main(){

	n=read();

	scanf("%lf",&k);

	rin(i,1,n) d[i]=read(),siz[i]=1;

	std::sort(d+1,d+n+1);

	rin(i,1,n) add_edge((int)floor(i/k),i);

	irin(i,n,1) siz[(int)floor(i/k)]+=siz[i];

	trav(i,0){int ver=e[i].to;loc=ver,kk=siz[ver];upd(1,1,n);}

	int cnt=1;

	rin(i,2,n+1){

		if(d[i]==d[i-1]){

			++cnt;

			continue;

		}

		irin(j,cnt,1){

			kk=j;int ret=query(1,1,n);ans[ret]=d[i-1];

			loc=ret,kk=-siz[ret];upd(1,1,n);

			trav(l,ret){

				int ver=e[l].to;

				loc=ver,kk=siz[ver];upd(1,1,n);

			}

		}

		cnt=1;

	}

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

	printf("\n");

	return 0;

}

			++cnt;

			continue;

		}

		irin(j,cnt,1){

			kk=j;int ret=query(1,1,n);ans[ret]=d[i-1];

			loc=ret,kk=-siz[ret];upd(1,1,n);

			trav(l,ret){

				int ver=e[l].to;

				loc=ver,kk=siz[ver];upd(1,1,n);

			}

		}

		cnt=1;

	}

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

	printf("\n");

	return 0;

}

巴特西

[BZOJ5249][九省联考2018]IIIDX：线段树+贪心

分析

代码

最新文章

热门文章