Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Đếm phần tử nhỏ hơn trong tập động

    Quản lý một đa tập (multiset) ban đầu rỗng. Xử lý qqq thao tác:

    • I x: thêm một bản sao của xxx vào tập.
    • D x: xoá một bản sao của xxx (nếu không có thì bỏ qua).
    • C x: in ra số phần tử hiện có trong tập nhỏ hơn xxx (đếm cả lặp).

    Sử dụng cây chỉ số nhị phân (Fenwick) kết hợp nén toạ độ offline để mỗi thao tác chạy O(log⁡q)O(\log q)O(logq).

    • Định dạng đầu vào:

      Dòng đầu chứa qqq. qqq dòng tiếp theo, mỗi dòng một ký tự I/D/C và một số nguyên xxx.

    • Ràng buộc đầu vào:

      1≤q≤2⋅1051 \le q \le 2\cdot10^51≤q≤2⋅105, ∣x∣≤109|x| \le 10^9∣x∣≤109.

    • Định dạng đầu ra:

      Với mỗi thao tác C, in kết quả trên một dòng.

    Ví dụ:

    Đầu vào:

    5
I 5
I 3
I 8
C 6
C 3

    Đầu ra:

    2
0

    Giải thích:

    Sau ba lệnh thêm, tập là {3,5,8}. Truy vấn C 6 đếm các phần tử nhỏ hơn 6 là {3,5} cho 2. Truy vấn C 3 đếm phần tử nhỏ hơn 3, không có nên 0.

    Đang tải editor...