#P5584. 「SWTR-1」Sunny's Crystals

    ID: 6277 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>2019线段树Special JudgeO2优化

「SWTR-1」Sunny's Crystals

背景

小 S\mathrm{S} 喜欢收集水晶。

题目描述

小 S\mathrm{S} 有 nn 个水晶,每个水晶有一个属性 did_i ,为这个水晶的价值。

有一天,小 A\mathrm{A} 来到了 小 S\mathrm{S} 家,让 小 S\mathrm{S} 把他的水晶排成一个序列,并且摧毁所有价值为 ww 的水晶。

但是,由于这个序列的特殊性,你的每次摧毁必须要满足:

  • 该水晶在序列里的位置必须要是 22 的次幂,即你只能摧毁在 2x2^x 这个位置上的水晶,0≤x≤log⁡2y0\leq x \leq \log_2 y 且为整数,其中 yy 为现在序列里水晶的个数。

摧毁后,所有在该水晶后面的水晶都会向前移动一格。

例如,水晶价值序列 6 10 4 7 86\ 10\ 4\ 7\ 8,你只能摧毁位置为 1,2,41,2,4 上的水晶。

如果摧毁 22 号水晶,序列就会变成 6 4 7 86\ 4\ 7\ 8。

为了节省时间,小 S\mathrm{S} 想知道最少多少次可以摧毁所有价值为 ww 的水晶,且第 ii 次摧毁的水晶初始位置是什么。

本题使用 Special Judge,如果有多种答案,任意输出一种即可。

输入格式

第一行两个整数 n,wn,w。

第二行,nn 个正整数 did_i。

输出格式

第一行一个整数 mm,表示最少可以摧毁所有 ww 的次数。

接下来一行 mm 个数,第 ii 个数表示 第 ii 次摧毁时被摧毁的水晶的初始位置是什么,用空格隔开。

5 4
1 4 2 4 5
2
4 2
5 2
1 2 2 2 2
4
2 3 4 5
5 8
6 10 4 7 8
2
4 5

提示


样例说明

样例 11:

先摧毁后面的 44,初始位置为 44,价值序列变成: 1 4 2 51\ 4\ 2\ 5。

再摧毁前面的 44,初始位置为 22。

总次数是 22 次。

样例 22:

先摧毁第 11 个 22,初始位置为 22,序列变成:1 2 2 21\ 2\ 2\ 2。

再摧毁剩下的第 11 个 22,初始位置为 33,序列变成:1 2 21\ 2\ 2。

再摧毁第一个 22,初始位置为 44,序列变成:1 21\ 2。

再摧毁第一个 22,初始位置为 55。

总次数是 44 次。


数据范围与约定

对于 15%15\% 的数据,有 n≤5n\leq5。

对于 25%25\% 的数据,有 n≤20n\leq20。

对于 30%30\% 的数据,有 n≤1000n\leq1000。

对于 35%35\% 的数据,有 n≤10000n\leq10000。

对于 50%50\% 的数据,有 n≤3×105n\leq3\times 10^5。

对于 80%80\% 的数据,有 n≤106n\leq10^6。

对于 100%100\% 的数据,有 1≤n≤3×106,1≤di≤400001\leq n\leq3\times 10^6,1\leq d_i\leq 40000,保证 ww 的个数不大于 1.5×1061.5\times 10^6。


碎掉的水晶在阳光下闪闪发光……