Bedao Grand Contest 11 - EASYQUERY

View as PDF

Submit solution


Points: 0.55 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy ~a~ độ dài ~n~ và ~q~ thông tin thuộc một trong ~3~ loại sau:

  • ~1\ l\ r\ x~ ~(1 \le l \le r \le n,\ 1 \le x \le 10^8)~: các phần tử trong đoạn ~l\ r~ được tăng thêm ~x~.

  • ~2\ i~: thông tin thứ ~i~ là thông tin sai (dữ liệu đảm bảo thông tin thứ ~i~ thuộc loại ~1~ hoặc loại ~2~ và thông tin thứ ~i~ đã xuất hiện trước đó).

  • ~3\ l\ r~ ~(1 \le l \le r \le n)~: tính tổng các số trong đoạn ~l\ r~.

Với mỗi truy vấn thuộc loại ~3~, in ra tổng cần tìm, biết rằng những thông tin đang không bị thông tin loại ~2~ chỉ vào thì chắc chắn là thông tin đúng, và không có hai thông tin loại ~2~ nào giống hệt nhau.

Input

  • Dòng đầu nhập ~2~ số ~n~ và ~q~ ~(1 \le n,\ q \le 10^5)~ ~-~ tương ứng là số phần tử của dãy ~a~ và số thông tin .

  • Dòng thứ hai nhập ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^8)~- tương ứng là các phần tử của dãy ~a~

  • Trong ~q~ dòng tiếp theo, mỗi dòng nhập một thông tin thuộc một trong ~3~ loại theo định dạng như đề bài.

Output

  • Với mỗi truy vấn thuộc loại ~3~, in ra tổng cần tìm.

Subtask

  • ~20\%~ số test khác có ~1 \le n, q \le 2000~.

  • ~80\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input

5 6
0 0 0 0 0
1 1 2 1
3 1 3
2 1
3 1 3
2 3
3 1 3

Sample Output

2
0
2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.