#PQJ466x2681. QOJ 466_2681

    ID: 2982 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HNOI 2019二分

QOJ 466_2681

第3 题:序列(sequence),运行时限2s,内存上限512M,100 分。

【问题描述】 给定一个长度为𝑛的序列𝐴1, … , 𝐴𝑛,以及𝑚个操作,每个操作将一个𝐴𝑖修改为𝑘。第一次修改 之前及每次修改之后,都要求你找到一个同样长度为𝑛的单调不降序列𝐵1, … , 𝐵𝑛,使得∑ (𝐴𝑖− 𝑛 𝑖=1 𝐵𝑖)2最小,并输出该最小值。需要注意的是每次操作的影响都是独立的,也即每次操作只会对当 前询问造成影响。为了避免精度问题,我们保证这个最小值是个分数,也即能表示为两个非负整 数相除的形式:𝑥/𝑦。那么你将要输出(𝑥∗𝑦𝑃−2)𝑚𝑜𝑑 𝑃的值,表示模意义下𝑥/𝑦的值。其中𝑃= 998244353是一个大质数。

【程序文件名】 源程序文件名为𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒. 𝑐𝑝𝑝/𝑐/𝑝𝑎𝑠。

【输入格式】 输入文件名为𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒. 𝑖𝑛。 第一行两个非负整数𝑛, 𝑚,代表序列长度和操作数。 第二行有𝑛个由空格隔开的正整数,代表序列𝐴1, … , 𝐴𝑛。 接下来𝑚行每行两个正整数𝑖, 𝑘,代表将𝐴𝑖修改为𝑘。

【输出格式】 输出文件名为𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒. 𝑜𝑢𝑡。 输出𝑚+ 1行每行一个整数,第𝑖行输出第𝑖−1次修改后的答案。特别的,第1行应为初始局面 的答案。

【输入输出样例】 sequence.in sequence.out 5 3 9 2 4 6 4 1 1 1 4 5 6 28 2 4 26

【样例解释】 第一个询问的最优𝐵序列为:{5 5 5 5 5}。 第二个询问的最优𝐵序列为:{1 2 4 5 5}。 第三个询问的最优𝐵序列为:{3 3 4 5 5}。 第四个询问的最优𝐵序列为:{5 5 5 6 6}。 样例是存在最优方案使𝐵𝑖皆为整数的特殊情况。

【数据范围】 对于前10%的数据,保证𝑛, 𝑚≤10,𝑘, 𝐴𝑖≤1000,且存在一种最优方案,使得𝐵𝑖皆为整数。

对于前30%的数据,保证𝑛, 𝑚≤100。 对于另外20%的数据,保证m = 0。 对于另外20%的数据,保证𝑛, 𝑚≤3 ∗104。 对于所有数据,保证3 ≤𝑛≤105,0 ≤𝑚≤105,1 ≤𝑘, 𝐴𝑖≤109。

【编译命令】 对于c++语言: g++ -o sequence sequence.cpp –lm –O2 对于c 语言: gcc -o sequence sequence.c –lm –O2 对于pascal 语言: fpc sequence.pas –O2