自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:12:13，当前版本为作者最后更新于2019-10-02 23:43:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\color{#00cfff}T3.\ Sunny's\ Crystals$

$\color{#00cfff}\text{题面}$

官方题解

$Sol\ 1\ :\ 15\ pts$

$n!$ 枚举，可过 $15\%$ 的点

代码就不贴了

$Sol\ 2:\ 30-35\ pts$

$n^2$ 贪心，可过 $30-35\%$ 的点

模拟每次摧毁

• 如果有可以摧毁的水晶，摧毁位置靠后的

（如果不是位置在最后，那么摧毁该水晶的时会影响到后面可摧毁的水晶）

• 否则摧毁当前序列第一个

（贪心思想，没有可摧毁的 $w$，则摧毁位置越前越好）

代码就不贴了

$Sol\ 3:\ 80-100\ pts$

$nlog(n)$，线段树维护贪心

线段树的常数巨大，如果你脸黑可能拿不到满分（毕竟只开了不加优化的标程 $+500ms$）

我们先找出所有 $w$，可以 $O(n)$ 求出第 $i$ 个 $w$ 到 在它之前第一个可以摧毁的位置 的距离，记为 $d_i$，共有 $c$ 个，记录初始位置 $pos_i$

也就是说，求出 $pos_i-v_i$，其中 $v_i\leq pos_i,v_i=2^x,x$ 为非负整数且 $v_i$ 要最大

接着在 $d_1-d_c$ 之间建线段树，维护区间最小值

仍然是模拟每次摧毁

• $1.$ 如果有可以摧毁的水晶，摧毁位置靠后的

这其实就是找到一个 $i$ 最大且 $d_i$ 为 $0$ 的 $i$，摧毁

接着把这个位置上的值赋为极大， $2147483647$ 或一个大于 $10^7$ 的数

然后它后面所有的 $d_{i+1},d_{i+2},\dots,d_c$ 都要 $-1$（这个能理解吧 $qwq$）

• $2.$ 否则求出 $d_1,d_2,\dots,d_c$ 中最小的数，记为 $l$，摧毁 $l$ 个位置为 $1$ 的水晶，$d_1,d_2,\dots,d_c$ 全部减去 $l$，再执行操作 $1$

简而言之，就是让你维护一个 区间修改，区间最小值 的线段树

代码

//by ALEX_WEI
#include<bits/stdc++.h>
using namespace std;
//pragma GCC optimize(3) 开了 O(3) 跑得飞快 , 妈妈再也不用担心我 TLE 啦 !
const int N=3e6+2;
const int inf=2e9+7;
inline void read(int &x)//建议写快读
{
	x=0;char s=getchar();
	while(!isdigit(s))s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=getchar();
}
inline int _min(int a,int b){return a<b?a:b;}//建议手写 min
int n,x,a,cnt,pow2=1,pos,ori[N],dis[N],els[N],t[N<<2],laz[N<<2],ans[N],now;
//ori 记录初始位置 , els 记录不是 w 的位置 , dis 为题解中的 pos[i]-v[i] , ans 为答案序列 , cnt 为题解中的 c
void build(int l,int r,int x)//建树
{
	if(l==r){t[x]=dis[l];return;}
	int m=l+r>>1;
	build(l,m,x<<1);
	build(m+1,r,x<<1|1);
	t[x]=_min(t[x<<1],t[x<<1|1]);
}
void push_down(int l,int r,int x)
{
	t[x<<1]-=laz[x];
	t[x<<1|1]-=laz[x];
	laz[x<<1]+=laz[x];
	laz[x<<1|1]+=laz[x];
	laz[x]=0;//清零
	t[x]=_min(t[x<<1],t[x<<1|1]);//更新
}
void update(int l,int r,int ql,int qr,int x)
{
	if(ql<=l&&r<=qr){laz[x]++,t[x]--;return;}
	int m=l+r>>1;
	if(m>=ql)update(l,m,ql,qr,x<<1);
	if(m<qr)update(m+1,r,ql,qr,x<<1|1);
	t[x]=_min(t[x<<1],t[x<<1|1]);//最小值
}
int get(int l,int r,int x)
{
	if(l==r){t[x]=inf;return l;}//返回的是编号 ! 
	push_down(l,r,x);//pushdown
	int m=l+r>>1,tmp;
	if(!t[x<<1|1])tmp=get(m+1,r,x<<1|1);//如果左边是 0, 往左边跑
	else tmp=get(l,m,x<<1);//否则往右边跑
	t[x]=_min(t[x<<1],t[x<<1|1]);//更新
	return tmp;
}
int main()
{
	read(n),read(x);
	for(int i=1;i<=n;i++){//O(n) 求 dis 数组
		read(a);
		if((pow2<<1)==i)pow2<<=1;
		if(a==x)ori[++cnt]=i,dis[cnt]=i-pow2;
		else els[++pos]=i;
	}
	build(1,cnt,1),pos=0;
	for(int i=1;i<=cnt;i++){
		if(t[1]){//t[1] 即为 min(dis[1],dis[2],...,dis[cnt]) 
			laz[1]+=t[1];//懒惰标记标上
			for(int j=1;j<=t[1];j++)
				ans[++now]=els[++pos];//从不是 w 的取 t[1] 个
			t[1]=0;//清零
		}
		int p=get(1,cnt,1);//求出可摧毁的水晶编号
		ans[++now]=ori[p];//摧毁掉 , 编号为初始位置
		if(p<cnt)update(1,cnt,p+1,cnt,1);//如果摧毁的不是最后一个 , 将 d[p+1],d[p+2],...,d[c] 减去 1
	}
	cout<<now<<endl;//输出
	for(int i=1;i<=now;i++)
		cout<<ans[i]<<" ";
	return 0;
}

求赞 $qwq$