trang chủ / đề bài / icpc26_mb_f

Dãy cảm biến liên thông

Đề bài

Mô tả

Một lưới phòng thủ quan trọng ở Khu vực 2026 dựa vào một dãy cảm biến tuyến tính gồm n nút giám sát, được đặt lần lượt từ 1 đến n. Mức hiệu chuẩn của các nút tạo thành một hoán vị p1,p2,…,pn của các số nguyên từ 1 đến n.

Để phân tích độ ổn định tín hiệu cục bộ, trung tâm điều khiển xem xét mọi đoạn con liên tiếp khác rỗng pl,pl+1,…,pr (với 1≤l≤r≤n). Với mỗi đoạn con như vậy, một đồ thị liên lạc vô hướng được xây dựng như sau:

  • Các đỉnh của đồ thị là các chỉ số {l,l+1,…,r}.
  • Với hai chỉ số i và j bất kỳ trong cửa sổ, l≤i<j≤r, có một cạnh vô hướng (i,j) khi và chỉ khi pi>pj.

Nói cách khác, hai nút cảm biến được nối trực tiếp khi và chỉ khi mức hiệu chuẩn của chúng tạo thành một nghịch thế. Một đoạn con được gọi là nhất quán khi và chỉ khi đồ thị cảm sinh của nó liên thông. Lưu ý rằng cửa sổ chỉ gồm đúng một đỉnh luôn được coi là liên thông.

Hãy xác định tổng số đoạn con liên tiếp khác rỗng có đồ thị nghịch thế cảm sinh liên thông.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên n (1≤n≤200000).
  • Dòng thứ hai chứa n số nguyên p1,p2,…,pn cách nhau bởi dấu cách, tạo thành một hoán vị của 1,2,…,n.

Dữ liệu ra

In ra một số nguyên duy nhất: số đoạn con liên tiếp tạo thành đồ thị liên thông.

Ràng buộc

  • 1≤n≤200000.
  • p là một hoán vị của các số nguyên từ 1 đến n.

Ví dụ

Input Output Giải thích
3
3 1 2
5 Đoạn [3,1] liên thông vì 3>1 tạo thành một cạnh. Đoạn [1,2] không có nghịch thế nên không liên thông. Ba đoạn một phần tử [3], [1], [2] hiển nhiên liên thông, và cả dãy [3,1,2] liên thông (cạnh (1,2) và (1,3)), tổng cộng 5 đoạn liên thông.
4
1 2 3 4
4 Hoán vị không có nghịch thế nào. Do đó mọi đoạn có độ dài ≥2 đều không có cạnh và không liên thông. Chỉ có 4 đoạn một phần tử là liên thông.
4
4 3 2 1
10 Mọi cặp phần tử đều tạo thành nghịch thế, nên đồ thị của mọi đoạn con là một đồ thị đầy đủ. Vậy cả 10 đoạn con liên tiếp khác rỗng đều liên thô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