trang chủ / đề bài / fixptrem

Xóa điểm bất động

Đề bài

Mô tả

Cho dãy a1,a2,…,an gồm n số nguyên dương. Trong một thao tác, bạn được chọn một chỉ số i thỏa mãn ai=i và xóa phần tử ai khỏi dãy; sau khi xóa, các phần tử phía sau dồn lên (chỉ số của chúng giảm đi 1).

Trọng số của dãy là số phần tử lớn nhất có thể xóa được bằng các thao tác trên.

Có q truy vấn độc lập, mỗi truy vấn cho hai số x,y: thay x phần tử đầu tiên và y phần tử cuối cùng của dãy bằng n+1 (khiến chúng không bao giờ xóa được). Hãy cho biết trọng số của dãy thu được. Mỗi truy vấn được thực hiện trên dãy ban đầu.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.
  • q dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y mô tả một truy vấn.

Dữ liệu ra

In ra q dòng, dòng thứ i là đáp án của truy vấn thứ i.

Ràng buộc

  • 1≤n,q≤3·105
  • 1≤ai≤n
  • x,y≥0 và x+y<n

Ví dụ

Input Output Giải thích
13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12
5
11
6
1
0
Truy vấn đầu tiên: dãy thành [×, ×, ×, 9, 5, 4, 6, 5, 7, 8, 3, 11, ×]. Lần lượt xóa các phần tử 5, 11, 6, 8, 7 (mỗi lần xóa, giá trị đúng bằng vị trí hiện tại), được 5 phần tử và không thể làm tốt hơn.
5 2
1 4 1 2 4
0 0
1 0
2
0
Truy vấn thứ nhất: xóa a1=1, dãy thành [4, 1, 2, 4] và phần tử cuối nằm ở vị trí 4 nên xóa được, tổng cộng 2. Truy vấn thứ hai: không có phần tử nào xóa được.

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