trang chủ / đề bài / tst25_arrng

Tổng chênh lệch lớn nhất

Đề bài

Mô tả

Bạn được cho một dãy số H gồm N phần tử và Q truy vấn, mỗi truy vấn gồm hai số nguyên dương L,R (1≤L≤R≤N). Với mỗi truy vấn, xét dãy số A={HL,HL+1,…,HR}, nhiệm vụ của bạn là sắp xếp lại dãy số A theo thứ tự bất kỳ sao cho tổng chênh lệch của hai phần tử liên tiếp bất kỳ trong dãy là lớn nhất có thể. Hay nói cách khác, bạn cần tối đa hóa giá trị của S=∑i=1R−L|Ai−Ai+1|.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên dương N và Q tương ứng với số lượng phần tử trong dãy H và số lượng truy vấn (1≤N,Q≤4×105).
  • Dòng thứ hai gồm N số nguyên dương H1,H2,…,HN tương ứng với giá trị của các phần tử trong dãy H (1≤Hi≤109).
  • Cuối cùng là Q dòng, mỗi dòng gồm hai số nguyên dương L,R mô tả các truy vấn (1≤L≤R≤N).

Dữ liệu ra

Với mỗi truy vấn, in ra kết quả trên một dòng là tổng chênh lệch tối đa có thể đạt được.

Ràng buộc

  • 1≤N,Q≤4×105.
  • 1≤Hi≤109.
  • 1≤L≤R≤N.

Subtasks

  • Subtask 1 (12% số điểm): N,Q≤20.
  • Subtask 2 (20% số điểm): N,Q≤2000.
  • Subtask 3 (15% số điểm): N,Q≤5×104.
  • Subtask 4 (15% số điểm): Hi≤100 với mọi i từ 1 đến N.
  • Subtask 5 (20% số điểm): N,Q≤15×104.
  • Subtask 6 (18% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
5 2
1 2 3 4 8
1 5
1 3
17
3
Truy vấn 1: xếp thành 3,1,8,2,4, tổng 2+7+6+2=17. Truy vấn 2: xếp thành 2,1,3, tổng 1+2=3.
6 3
5 1 9 2 6 7
1 6
2 6
3 3
27
25
0
Ví dụ bổ sung (không có trong đề gốc). Truy vấn 1: 5,9,1,7,2,6, tổng 4+8+6+5+4=27. Truy vấn 2: 6,1,9,2,7, tổng 5+8+7+5=25. Truy vấn 3: chỉ có một phần tử nên tổng bằng 0.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0