WA在#10求助
  • 板块CF474E Pillars
  • 楼主YamadaRyou
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/11/11 20:49
  • 上次更新2023/11/4 00:51:38
查看原帖
WA在#10求助
203008
YamadaRyou楼主2021/11/11 20:49
#include<stdio.h>
#include<algorithm>
struct{
	int maxid,lc,rc;
}tree[300000<<1|1];
long long a[300001],b[900001];int f[300001],nxt[300001],n,d,m,tot;
int build(int l,int r){
	int x=++tot;
	if(l!=r){
		int mid=l+r>>1;
		tree[x].lc=build(l,mid),tree[x].rc=build(mid+1,r);
	}
	return x;
}
int query(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return tree[x].maxid;
	int mid=l+r>>1,ans=0;
	if(ql<=mid)ans=query(tree[x].lc,l,mid,ql,qr);
	if(mid<qr){
		int tmp=query(tree[x].rc,mid+1,r,ql,qr);
		if(f[tmp]>f[ans])
			ans=tmp;
	}
	return ans;
}
void change(int x,int l,int r,int k,int id){
	if(l==r){
		if(f[tree[x].maxid]<f[id])tree[x].maxid=id;
		return;
	}
	int mid=l+r>>1;
	if(mid<k)change(tree[x].rc,mid+1,r,k,id);
	else change(tree[x].lc,l,mid,k,id);
	if(f[tree[tree[x].lc].maxid]>f[tree[tree[x].rc].maxid])tree[x].maxid=tree[tree[x].lc].maxid;
	else tree[x].maxid=tree[tree[x].rc].maxid;
}
int getkey(int x){
	int l=1,r=m;
	for(;l<r;){
		int mid=l+r>>1;
		if(b[mid]<x)l=mid+1;
		else r=mid;
	}
	return l;
}
int main(){
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n;++i)scanf("%lld",a+i),b[i]=a[i],b[i+n]=a[i]-d,b[i+(n<<1)]=a[i]+d;;
	std::sort(b+1,b+3*n+1);
	m=std::unique(b+1,b+3*n+1)-b-1;
	build(1,m);
	int ans=0;
	for(int i=n;i;--i){
		nxt[i]=query(1,1,m,1,getkey(a[i]-d));int tmp=query(1,1,m,getkey(a[i]+d),m);
		if(f[nxt[i]]<f[tmp])nxt[i]=tmp;
		f[i]=f[nxt[i]]+1;
		change(1,1,m,getkey(a[i]),i);
		if(f[i]>f[ans])ans=i;
	}
	printf("%d\n",f[ans]);
	for(int i=ans;i;i=nxt[i])printf("%d ",i);
	return 0;
}
2021/11/11 20:49
加载中...