传统题 3000ms 256MiB

线段树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

本题的评测时间较长,若发现有恶意利用此题堵塞评测队列的,我们会采取包括但不限于禁赛等措施

线段树是一种常见的数据结构。线段树可以在均摊O(log2(n))O(log_2(n))的时间复杂度下进行很多区间操作,包括区间修改,区间查询,区间赋值,区间取模,区间学高数,区间挂科,区间cosplay,区间ak等等操作。

线段树有很多建树方法。以下为一种方法的伪代码:(aia_i是我们想在上面建线段树的数组,bib_i是线段树数组)

a,b是两个不同的数组
Function build(l,r,idx):
   if l equals r Then:
        {
           b[idx]=a[l]
        }
   else
        {
           mid=(l+r)/2
           使mid向下取整
           build(l,mid,idx*2)
           build(mid+1,r,idx*2+1)
           b[idx]=b[idx*2]+b[idx*2+1]
        }

我们只需要调用build(1,n,1)build(1,n,1),就可以对数组aa建线段树,线段树数组为bb

根据上面建好的线段树,我们可以在O(log2(n))O(log_2(n))时间复杂度内查询某个区间的和

kuro在刚学完线段树时,为这个数据结构的精妙感到惊叹,他很好奇,对于一颗线段树,树上的所有点的权值组成的集合是怎么样的呢?kuro很快知道了这个问题的答案,并决定将这个问题反过来问你:对于一个集合a(ai≠aj)a(a_i \neq a_j),是否存在一个子集cc,使得cc是一颗有nn个节点的线段树的所有点的权值组成的集合,并希望你能将线段树数组输出。

Input Format

第一行为两个整数$m,n(1 \leq m \leq 10^3,1 \leq n < 2^{18},\exists i(i \in N^+ ),$使得n=2i−1n=2^i-1成立)),代表集合aa的元素数和线段树的节点数

第二行为mm个整数ai(1≤ai≤1018)a_i(1 \leq a_i \leq 10^{18}),表示集合aa

Output Format

第一行包含输出一行"Yes"或"No"(都不包含双引号)

"Yes"表示可以构成线段树,"No"表示不能构成线段树。

注意:你可以以任何大小写方式输出答案,例如"Yes""YEs""yEs"都会被认为是输出了"Yes","NO""nO"都会被认为是输出了"No"

如果输出了"Yes",还需要输出第二行包含nn个整数bi(bi∈a)b_i(b_i \in a),表示线段树数组bb

如果有多种组成方式,你可以输出任何一种。

Sample

输入 #1

3 3
1 2 4

输出 #1

Yes
4 2 2

输入 #2

5 7
114 514 1919 810 1

输出 #2

No

重庆邮电大学第十八届ACM程序设计大赛(网络赛)

未参加
状态
已结束
规则
XCPC
题目
10
开始于
2024-12-14 0:00
结束于
2024-12-16 0:00
持续时间
48 小时
主持人
参赛人数
2