| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P162PROB - ROUND 2B - Box box |
Box Box là 1 streamer game online điện tử nổi tiếng, trong 1 event giáng sinh, Box Box có 1 trò chơi nho nhỏ dành cho các fan hâm mộ như sau:
Ban đầu Box Box có 1 mảng vòng tròn chứa n phần tử: a[0], a[1], a[2], … , a[n-1].
Anh có 2 loại truy vấn:
+ Truy vấn loại 1 (l, r, v): anh sẽ cộng vào tất cả các phần tử trong đoạn [l, r] thêm v.
+ Truy vấn loại 2 (l, r): anh sẽ hỏi các fan xem phần tử nhỏ nhất trong đoạn [l, r] có giá trị bằng bao nhiêu?
Mảng vòng tròn là các phần tử của mảng được xếp thành vòng tròn đúng theo thứ tự a[0], a[1], …, a[n-1], và phần tử a[0] sẽ xếp cạnh phần tử a[n-1]. Vậy nên nếu n = 5, truy vấn l = 3, r = 1 thì đoạn [3, 1] = {3, 4, 0, 1}
Nếu trả lời đúng tất cả các truy vấn 2 từ Box Box, người chơi sẽ nhận được dàn PC khủng nhất hiện nay. Iron man là người đam mê công nghệ, và anh rất muốn sở hữu dàn PC trên, bạn hãy giúp Ironman nhé.
Input
Dòng đầu tiên nhập số nguyên n (1 <= n <= 200 000).
Dòng tiếp theo nhập n phần tử ban đầu của mảng: a[0], a[1], a[2], … , a[n-1] (-106 <= a[i] <= 106, a[i] là số nguyên).
Dòng thứ 3 nhập số nguyên m (0 <= m <= 200 000).
m dòng tiếp theo, mỗi dòng nhập 1 truy vấn. Nếu dòng gồm 3 số nguyên l, r ,v (0 <= l, r < n; (-106 <= v <= 106) thì đây là truy vấn 1. Còn nếu dòng gồm 2 số nguyên l, r (0 <= l,r < n) thì đây là truy vấn 2
Output
Với mỗi truy vấn 2, in ra trên 1 dòng 1 số nguyên là kết quả của truy vấn đó.
Example
Input:4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1 Output:1
0
0
| Được gửi lên bởi: | adm |
| Ngày: | 2016-02-20 |
| Thời gian chạy: | 1s-3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
