B. Липшицын дараалал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дурын -ийн хувьд $|f(x) - f(y)| ≤ K*|x - y|$ тэнцэтгэл биш биелдэг байхаар $K$ гэсэн бодит тоо олддог бол функцыг Липшицын тасралтгүй функц гэнэ. Бид үүний дискрет тохиолдлыг авч үзнэ.

дарааллын хувьд үүний Липшицийн тогтмол гэдгээр дараахь гэсэн тоог ойлгоно:

  • хэрэв $n < 2$ бол
  • хэрэв $n ≥ 2$ бол ($i,j$ нь $1 ≤ i < j ≤ n$ байхаар гүйж байх үеийн максимум утга)

Өөрөөр хэлбэл нь дурын $1 ≤ i, j ≤ n$ - ийн хувьд $|h[i] - h[j]| ≤ L*|i - j|$ байх хамгийн бага сөрөг биш тоо юм.

Чамд $n$ урттай гэсэн дараалал өгөгдсөн. Мөн $[l, r]$ гэсэн бүтэцтэй $q$ ширхэг хүсэлт өгөгдсөн. Хүсэлт бүрт дэд дарааллын авч үзэн -ийн дэд дараалал бүрийн Липшицын тогтмолуудын нийлбэрийг ол.

Оролт

Эхний мөрөнд дарааллын урт болон хүсэлтийн тоог илэрхийлэх $n$ ба $q$ ($2 ≤ n ≤ 100 000$ and $1 ≤ q ≤ 100$) гэсэн хоёр бүхэл тоо байна.

Хоёр дахь мөрөнд $n$ ширхэг () бүхэл тоонууд зайгаар тусгаарлагдан байна.

Дараагийн $q$ мөрөнд хүсэлтүүд өгөгдөнө. $i$ дэх мөрөнд $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} < r_{i} ≤ n$) бүхэл тоонууд байна.

Гаралт

Хүсэлт бүрийн хариуг өгөгдөлд байгаа дарааллаар нь хэвлэ. $i$ дэх хүсэлтэнд -ийн бүх дэд дарааллуудын Липшицын тогтмолуудын нийлбэрийг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9
Гаралт
17
82
23
210
Оролт
7 6
5 7 7 4 6 6 2
1 2
2 3
2 6
1 7
4 7
3 5
Гаралт
2
0
22
59
16
8

Тэмдэглэл

Эхний жишээний эхний хүсэлтэнд -ийн ядаж хоёр урттай дэд дарааллуудын Липшицын тогтмолууд нь:

Хариу нь эдгээрийн нийлбэр байна.

Сэтгэгдлүүдийг ачааллаж байна...