【SWTR-01】Sweet Round 01 T3 Sunny's Crystals

· · 题解

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

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

官方题解

Sol\ 1\ :\ 15\ pts 代码就不贴了 --- $Sol\ 2:\ 30-35\ pts 模拟每次摧毁 - 如果有可以摧毁的水晶，摧毁位置靠后的 **（如果不是位置在最后，那么摧毁该水晶的时会影响到后面可摧毁的水晶）** - 否则摧毁当前序列第一个 （贪心思想，没有可摧毁的 $w$，则摧毁位置越前越好） 代码就不贴了 --- $Sol\ 3:\ 80-100\ pts 线段树的常数巨大，如果你脸黑可能拿不到满分（毕竟只开了不加优化的标程 $+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 之间建线段树，维护区间最小值

仍然是模拟每次摧毁

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

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

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

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

代码

//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