#P9599. [JOI Open 2018] 木琴

[JOI Open 2018] 木琴

题目背景

特别提醒,由于洛谷交互机制的特殊性,你不能在程序中引用 xylophone.h,而需要把 xylophone.h 中的内容加入文件的开头。即,在程序中 solve 函数的前面加入以下几行语句:

void solve(int N);
int query(int s, int t);
void answer(int i, int a);

题目描述

木琴是一种乐器,人可以通过敲击木条来演奏它。单个木条总是发出同样音高的音,因此一个木琴包含不同种音高的木条。

JOI 君买了一个有 NN 个木条的木琴。这 NN 个木条排成一排,从左到右编号为 11NN。编号为 i (1iN)i\ (1\le i\le N) 的木条能发出音高为 Ai (1AiN)A_i\ (1\le A_i\le N) 的音。不同的木条发出不同音高的音。他知道音高最低的木条要比音高最高的编号小。

因为 JOI 君不知道每个木条的音高是什么,他决定研究这些木条的音高。

JOI 有一种独特的音感,当他连续听到多个音时,他能分辨出最高音和最低音差多少。他可以一次敲击一些木条,然后听它们发出的声音。也就是说,对于两个整数 sst (1stN)t\ (1\le s\le t\le N),他可以连续敲击编号从 sstt​ 的木条,以知道 As,As+1,,AtA_s,A_{s+1},\ldots ,A_t​ 中最大值与最小值的差。

他想在 10 00010\ 000 次敲击之内知道每个木条的音高。


【实现细节】

你需要实现函数 solve 以求出每个木条的音高。

  • solve(N)

    • NN:木条的数量。
    • 这个函数每个测试点调用恰好一次。

你的程序可以调用评分器实现的如下函数。

  • query(s, t)

    这个函数返回在给定区间中木条音高最大值与最小值的差。

    • s,ts, tss 是要敲击的木条区间中第一个数,tt 是最后一个数。也就是说,你需要敲击编号在 [s,t][s,t] 区间内的所有木条。
    • 必须保证 1stN1\le s\le t\le N
    • 你不能调用 query 函数超过 10 00010\ 000 次。
    • 如果上述条件不满足,你的程序会被判为 Wrong Answer
  • answer(i, a)

    你的程序应当用这个函数回答每个木条的音高。

    • i,ai, a:这意味着你回答了 AiA_i 的值为 aa,其中 AiA_i 指木条 ii 的音高。
    • 必须保证 1iN1\le i\le N
    • 你不能对于相同的 i\texttt i 调用超过一次这个函数。
    • 你必须在函数 solve\texttt{solve} 结束前调用恰好 NN 次此函数。
    • 如果上述条件不满足,你的程序会被判为 Wrong Answer
    • 如果你的回答与实际音高有不同,你的程序会被判为 Wrong Answer

暂不支持 Java 与 Pascal 提交的测评。

提示

【样例交互】

一个对于 N=5,(A1,A2,A3,A4,A5)=(2,1,5,3,4)N=5,(A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4) 的样例交互过程如下。

调用 返回值
query(1, 5)\texttt{query(1, 5)}
44
answer(1, 2)\texttt{answer(1, 2)}
query(3, 5)\texttt{query(3, 5)}
22
answer(2, 1)\texttt{answer(2, 1)}
answer(3, 5)\texttt{answer(3, 5)}
answer(5, 4)\texttt{answer(5, 4)}
answer(4, 3)\texttt{answer(4, 3)}

【数据范围】

所有子任务满足以下限制:

  • 1AiN (1iN)1\le A_i\le N\ (1\le i\le N)
  • AiAj (1i<jN)A_i\neq A_j\ (1\le i<j\le N)
  • 对于满足 Ai=1,Aj=NA_i=1,A_j=Niijj,满足 i<ji<j​。

本题有三个子任务。子任务分值及附加限制如下表所示:

子任务编号 分值 NN
11 1111 2N1002\le N\le 100
22 3636 2N1 0002\le N\le 1\ 000
33 5353 2N5 0002\le N\le 5\ 000