A10234 | $Xors on Segments$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given an array with $n$ integers $a_{i}$ and $m$ queries. Each query is described by two integers $(l_{j},r_{j})$ . Let's define the function ![](/uploads/acgo/image/266538a7562c189f_6a73068bed49.jpeg). The function is defined for only $u<=v$ . For each query print the maximal value of the function $f(a_{x},a_{y})$ over all $l_{j}<=x,y<=r_{j},\ a_{x}<=a_{y}$ .

The first line contains two integers $n,m$ ( $1<=n<=5·10^{4},\ 1<=m<=5·10^{3}$ ) — the size of the array and the number of the queries. The second line contains $n$ integers $a_{i}$ ( $1<=a_{i}<=10^{6}$ ) — the elements of the array $a$ . Each of the next $m$ lines contains two integers $l_{j},r_{j}$ ( $1<=l_{j}<=r_{j}<=n$ ) – the parameters of the $j$ -th query.

For each query print the value $a_{j}$ on a separate line — the maximal value of the function $f(a_{x},a_{y})$ over all $l_{j}<=x,y<=r_{j},\ a_{x}<=a_{y}$ .

输入 #1

6 3
1 2 3 4 5 6
1 6
2 5
3 4

输出 #1

7
7
7

输入 #2

1 1
1
1 1

输出 #2

输入 #3

6 20
10 21312 2314 214 1 322
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 5
5 6
6 6

输出 #3

C++ 编辑器

输入

输出