Bật đèn

View as PDF
Submit solution
Points: 0.18 (partial)
Time limit: 0.45s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
USACO November 2008
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bác John giữ cho đàn bò thông minh bằng cách để chúng chơi các đồ chơi phát triển trí tuệ. Một trong các trò chơi là các ngọn đèn trong chuồng. Mỗi trong số ~N~ ~(2 \le N \le 10^{5})~ con bò được đánh số từ ~1~ ...~N~ có treo một ngọn đèn màu.

Vào đầu buổi tối, tất cả đèn đều tắt. Đàn bò điều khiển các ngọn đèn bằng ~N~ công tắc; bấm công tắc ~i~ đổi trạng thái của đèn ~i~ từ tắt sang bật hoặc ngược lại.

Đàn bò đọc và thực thi một danh sách gồm ~M~ ~(1 \le M \le 10^{5})~ thao tác mô tả bởi một trong hai số nguyên ~(0 \le~ thao tác ~\le 1)~.

Thao tác thứ nhất (mô tả bởi số ~0)~ theo sau bởi hai số nguyên ~S_i~ và ~E_i~ ~(1 \le S_i \le E_i \le N)~ cho biết công tắc đầu và công tắc cuối. Đàn bò sẽ bấm mỗi công tắc từ ~S_i~ đến ~E_i~ đúng một lần.

Thao tác thứ hai (mô tả bởi số ~1)~ yêu cầu đàn bò đến xem có bao nhiêu ngọn đèn giữa ~S_i~ và ~E_i~ ~(1 \le S_i \le E_i \le N)~ đang bật. Hãy giúp bác John đảm bảo rằng đàn bò trả lời đúng bằng cách xử lý danh sách và trả về các kết quả đúng.

Input

  • Dòng ~1~: Hai số nguyên cách nhau bởi khoảng trắng: ~N~ và ~M~
  • Dòng ~2~ ...~M+1~: Mỗi dòng chứa một thao tác với ba số nguyên cách nhau bởi khoảng trắng: thao tác, ~S_i~, và ~E_i~

Output

  • Dòng ~1~ ...số truy vấn: Với mỗi truy vấn, in ra kết quả là một số nguyên trên một dòng.

Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

Sample Output

1
2

Comments

Please read the guidelines before commenting.


  • -57
    vqt  commented on July 2, 2022, 2:10 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -29
      tqv  commented on July 2, 2022, 10:14 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -31
      hh123123  commented on July 2, 2022, 4:07 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -41
    VLTisME986  commented on June 22, 2022, 8:13 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -25
      nguyendanghau2006  commented on July 1, 2022, 5:02 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -26
      fuocs  commented on June 29, 2022, 5:36 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -27
      hh123123  commented on June 22, 2022, 11:00 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -67
    MrMinhFly  commented on May 27, 2021, 1:00 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -34
      kimya  commented on Oct. 5, 2021, 4:17 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -78
    MrMinhFly  commented on May 26, 2021, 12:23 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.