TWICE

Xem PDF



Tác giả:
Dạng bài
Điểm: 400 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

SPyofgame đang thực hiện một thử thách: đạt được mức Expert codeforces trong 1 tháng hoặc mất 50k. Trong lúc luyện tập, anh ấy gặp 1 bài toán như sau:

Cho mảng \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots A_N\), và \(Q\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L,R\), và câu trả lời cho truy vấn là có bao nhiêu giá trị khác nhau xuất hiện đúng 2 lần trong đoạn \([L,R]\) của mảng \(A\).

Input

  • Dòng thứ nhất chứa hai số nguyên \(N,Q\) \((1 \leq N, Q \leq 5*10^5)\).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots A_N\) \((A_i \leq 10^9)\)
  • \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L,R\) \((1 \leq L \leq R \leq N)\)

Output

  • In ra \(Q\) dòng, dòng thứ \(i\) là câu trả lời cho truy vấn thứ \(i\).

Example

Test 1

Input
5 1
1 2 1 1 1
1 3 
Output
1

Bình luận


  • 0
    huyhau6a2 8:09 p.m. 14 Tháng 1, 2022

    Thuật toán Mo là cái gì ta?


    • 0
      vinhntndu 8:23 p.m. 26 Tháng 7, 2020

      bài này giảm giới hạn thời gian được không ạ

      1 phản hồi

      • 1
        vinhntndu 6:48 p.m. 21 Tháng 7, 2020

        Subtask: 40% số test có N và Q không vượt quá 5000


        • -1
          SPyofgame 11:20 a.m. 13 Tháng 7, 2020

          :thonk: đề này quen quen

          1 phản hồi