← 返回比赛

已结束 COCR 提高赛 #1

← 上一题下一题 →

A4764 | $定点の轰炸$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

偏心\dots\dots？ JW 的父亲是一个轰炸机飞行员，一天，他接到一个任务：对城市 $F$ 轰炸 $Q$ 次！当然，任务远没有这么简单，对于第 $i$ 次轰炸任务，他需要在 $[l_i,r_i]$ 内选择一个整数点轰炸。JW 的父亲在执行任务前，偶然发现这是他好朋友的家乡。于是他私自决定了：轰炸最高的建筑的位置！（因为他好朋友的房子很矮）。而且，为了保护好朋友的房子，JW 的父亲都会等待人们重修好再进行下一次轰炸。但是，他不知道在每次任务应该轰炸哪个位置，于是请 JW 班里的天才——你来解决。 当然，这个问题太难了，于是，JW 的父亲把这个问题简化了一下：这个城市可以看作一条长为 $N$ 个线段，$i$ 点上是房子 $i$，高 $h_i$ 米，每次给出范围 $l,r$，求出 $[l,r]$ 中的点 $i$，使 $h_i$ 最大。

输入格式

输入共 $N + Q + 1$ 行： 第一行是两个正整数 $N,Q$，表示房子个数和轰炸次数； 第二行有 $N$ 个正整数，第 $i$ 个数 $h_i$ 代表房子 $i$ 的高度； 接下来有 $Q$ 行，每行是两个正整数 $l,r$，表示可以选择的轰炸范围。

输出格式

输出为 $Q$ 行： 第 $i$ 行只有一个正整数，表示对于轰炸 $i$，要选择的房子的编号。如果有多个解，输出最小的一个。

输入输出样例

输入 #1

11 5
3 5 1 8 3 5 9 10 4 6 6
1 5
4 7
8 9
6 10
10 11

输出 #1

【数据保证】 对于所有数据，保证： $1 \leq l \leq r \leq N \leq 3 \times 10^5$，$1 \leq Q \leq 10^6$,$1\leq h_i \leq 10^9$ 测试点$N\leq$1~5$10^3$6~10$3\times10^5$ 本题测试点等分。 【样例解释】 本题无样例解释。

C++ 编辑器

输入

输出