#2323. 线段树
线段树
线段树
题目描述
NOI2016 浙江省队选拔赛第二试 线段树 线段树 【问题描述】 小Yuuka 遇到了一个题目:有一个序列 𝑎1, 𝑎2, ⋯, 𝑎𝑛, 𝑞 次操作,每次把一 个区间内的数改成区间内的最大值,问最后每个数是多少。小Yuuka 很快地就使 用了线段树解决了这个问题。 于是充满智慧的小Yuuka 想,如果操作是随机的,即在这 𝑞 次操作中每次等 概率随机地选择一个区间 𝑙, 𝑟 1 ≤𝑙≤𝑟≤𝑛 ,然后将这个区间内的数改成区间 内最大值(注意这样的区间共有 𝑛(𝑛+1) 2 个),最后每个数的期望大小是多少呢? 小Yuuka 非常热爱随机,所以她给出的输入序列也是随机的(随机方式见数 据规模和约定)。 对于每个数,输出它的期望乘 𝑛(𝑛+1) 2
𝑞 再对109 + 7取模的值。 【输入格式】 输入文件segment.in 第一行包含 2 个正整数 𝑛, 𝑞 ,表示序列里数的个数和操 作的个数。 接下来 1 行,包含 𝑛 个非负整数 𝑎1, 𝑎2, ⋯, 𝑎𝑛。 【输出格式】 输出文件为segment.out。 输出共 1 行,包含 𝑛 个整数,表示每个数的答案。 【样例输入1】 5 5 1 5 2 3 4 【样例输出1】 3152671 3796875 3692207 3623487 3515626 【样例输入输出2】 见选手目录下的segment/segment_ex1.in 与segment/segment_ex1.ans。 注意样例输入输出1 和2 不满足数据规模和约定中的生成方式。
NOI2016 浙江省队选拔赛第二试 线段树 【样例输入输出3】 见选手目录下的segment/segment_ex2.in 与segment/segment_ex2.ans。 【数据规模和约定】 对于所有的测试数据,保证序列中数的大小不超过 109 ,即 𝑎𝑖≤109 ,并 且每个数是 0 到 109 之间的随机整数。 各测试点满足以下约定: 测试点 𝑛 q 约定 1 ≤5 ≤5 无 2 ≤8 ≤400 3 ≤12 4 ≤30 5 ≤50 6 ≤100 7 8 ≤400 9 10
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 5
1 5 2 3 4
3152671 3796875 3692207 3623487 3515626
样例 2
12 200
1997 1019 2529 19 1996 1677 2787 1598 2382 520 724 2000
846086023 652398328 159451033 551654274 431090738 774624653 172305990 854553091 820969655 792507301 472638972 63881831