trang chủ / đề bài / icpc22_mb_i

Dãy con tăng dài nhất

Đề bài

Mô tả

Leon là một sinh viên chăm chỉ, thường dành thời gian rảnh để suy ngẫm về các dãy số nguyên. Hôm nay, cậu đặc biệt quan tâm đến các dãy tăng.

Một dãy con được tạo thành bằng cách xóa không hoặc nhiều phần tử khỏi một dãy và giữ nguyên thứ tự các phần tử còn lại. Dãy con tăng dài nhất của một dãy là dãy con dài nhất có các phần tử tăng ngặt. Dãy con này không nhất thiết duy nhất. Ví dụ, dãy con tăng dài nhất của dãy (1,2,4,3) có thể là (1,2,3) hoặc (1,2,4), cả hai đều có độ dài 3.

Leon đưa cho bạn bài toán sau:

Cho dãy X, gọi Y là một dãy con của X. Độ dài lớn nhất có thể của Y là bao nhiêu, sao cho độ dài dãy con tăng dài nhất của Y không vượt quá K?

Bài này quá dễ với bạn, nên Leon quyết định hỏi thêm. Cậu đưa cho bạn một dãy ban đầu A gồm N số nguyên, sau đó đặt Q câu hỏi. Bạn vẫn giải bài toán trên, nhưng dãy X và số nguyên K thay đổi theo từng câu hỏi: Leon cho trực tiếp số nguyên K, và cho số nguyên M, nghĩa là dãy X gồm M phần tử đầu tiên của dãy A.

Với mỗi câu hỏi, hãy đưa ra đáp án của bài toán trên với dãy X và số nguyên K tương ứng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên N và Q, trong đó N là số phần tử của dãy A và Q là số câu hỏi (1≤N≤50000, 1≤Q≤200000).

Dòng thứ hai chứa N số nguyên A1,A2,…,AN là các phần tử của dãy A (1≤Ai≤50000).

Q dòng tiếp theo, dòng thứ i chứa hai số nguyên Mi và Ki: bạn phải giải bài toán trên với Mi phần tử đầu tiên của A và số nguyên Ki (1≤Ki≤Mi≤N).

Dữ liệu ra

Với mỗi câu hỏi, in ra một dòng chứa đáp án.

Ràng buộc

  • 1≤N≤50000, 1≤Q≤200000.
  • 1≤Ai≤50000.
  • 1≤Ki≤Mi≤N.

Ví dụ

Input Output Giải thích
11 6
9 6 3 1 5 12 8 4 2 2 2
5 1
7 2
9 1
9 2
11 1
11 11
4
6
5
8
7
11
Câu 1: với X=(9,6,3,1,5) chọn Y=(9,6,3,1), dãy con tăng dài nhất của Y có độ dài 1. Câu 2: với X=(9,6,3,1,5,12,8) chọn Y=(9,6,3,1,12,8), độ dài 2. Câu 3: chọn Y=(9,6,5,4,2). Câu 4: chọn Y=(9,6,3,1,12,8,4,2). Câu 5: chọn Y=(9,6,5,4,2,2,2). Câu 6: chọn cả dãy, dãy con tăng dài nhất có độ dài 3.
6 6
3 3 1 2 2 4
2 1
4 1
5 1
5 2
6 1
6 2
2
3
4
5
4
5
Dãy tăng phải tăng ngặt nên hai số bằng nhau không tạo thành dãy tăng: câu 1 chọn (3,3), câu 3 chọn (3,3,2,2). Câu 6: với K=2 chọn (3,3,1,2,2) hoặc (3,3,2,2,4), không thể chọn cả 6 phần tử vì (1,2,4) tăng.

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