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

    ID: 4515 Type: RemoteJudge 2000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>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 这个位置上的水晶,0xlog2y0\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

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

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

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

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

总次数是 44 次。


数据范围与约定

对于 15%15\% 的数据,有 n5n\leq5

对于 25%25\% 的数据,有 n20n\leq20

对于 30%30\% 的数据,有 n1000n\leq1000

对于 35%35\% 的数据,有 n10000n\leq10000

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

对于 80%80\% 的数据,有 n106n\leq10^6

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


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