Khai bút đầu xuân

Xem dạng PDF

Gửi bài giải


Điểm: 0,37 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
SPOJ
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mùng ~1~ Tết, Nuga quyết định khai bút đầu xuân bằng cách giải một bài tập tin rất khó mà bạn ấy đã thấy trong một giấc mơ.

Cho một dãy số nguyên dương. Tính xem có bao nhiêu dãy con gồm các phần tử liên tiếp của nó mà có số lượng phần tử khác nhau nằm trong đoạn [~L~, ~U~].

Sau ~2~ tiếng ngồi cắn bút mà không giải xong, Nuga quyết định nhờ các bạn đội tuyển tin giúp đỡ. Nuga sẽ rất biết ơn nếu các bạn giải được bài tập này, và bạn ấy sẽ lì xì cho các bạn nhân dịp đầu năm mới.

Input

Dòng đầu tiên chứa các số nguyên dương ~N~, ~L~, ~U~. Sau đó là ~N~ dòng, mỗi dòng chứa một số nguyên dương ~X~ là một phần tử của dãy số.

Output

Một dòng duy nhất chứa một số nguyên thể hiện số dãy con có số lượng phần tử khác nhau nằm trong đoạn [~L~, ~U~].

Sample Input

4 1 2
231
19
7
19

Sample Output

8

Giới hạn

  • ~1 \le L \le U \le N \le 2^{20}~
  • ~1 \le X \le 2^{31} - 1~

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 11
    anhtri  đã bình luận lúc 18, Tháng 7, 2023, 16:34

    My Solution:

    ĐPT: ~O(N * log_2N)~

    2 con trỏ + ý tưởng giống tính tổng đoạn [L, R] trong mảng cộng dồn.

    Gọi ~calc(x)~ là số lượng dãy con có số phần tử khác nhau không vượt quá ~x~ trong đoạn [1, N].

    Nếu chưa gặp dạng này bao giờ thì bạn có thể tham khảo qua phần Edu của Codeforces (nhớ Enroll phần pilot course trước nhé): link, phần Segment with Small Set nhé.

    ~res~ = ~calc(U) - calc(L - 1)~.

    code tham khảo: link.


  • -9
    trongtenlinhcbhk64  đã bình luận lúc 4, Tháng 7, 2023, 16:29 sửa 3

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 1
    YukatouArimotou  đã bình luận lúc 29, Tháng 6, 2023, 13:31

    có thể giải thích rõ hơn đề bài được không ạ :<


    • -4
      trongtenlinhcbhk64  đã bình luận lúc 2, Tháng 7, 2023, 16:28

      đếm số đoạn con liên tiếp có số phần tử khác nhau ( tạm gọi là x ) thỏa mãn L <= x <= U thôi


  • -14
    tboros2  đã bình luận lúc 26, Tháng 11, 2022, 9:16

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.