← 返回题目列表

Codeforces · 52/C

C. 圆形 RMQ

中文机器翻译题面 查看原题

给定一个循环数组 a0, a1, ..., an - 1。它有两种类型的运算:

- inc(lf, rg, v) — 此操作将段 [lf, rg] 上的每个元素(包含)增加 v;
- rmq(lf, rg) — 此操作返回段 [lf, rg] 上的最小值(包含)。

假设线段是循环的,因此如果n = 5且lf = 3,rg = 1,则表示索引序列:3,4,0,1。

编写程序来处理给定的操作序列。

输入

第一行包含整数 n (1 ≤ n ≤ 200000)。下一行包含数组的初始状态:a0, a1, ..., an - 1 (- 106 ≤ ai ≤ 106), ai 是整数。第三行包含整数 m (0 ≤ m ≤ 200000),m — 操作数。接下来的 m 行每行包含一个操作。如果 line 包含两个整数 lf, rg (0 ≤ lf, rg ≤ n - 1) 则表示 rmq 运算,包含三个整数 lf, rg, v (0 ≤ lf, rg ≤ n - 1; - 106 ≤ v ≤ 106) — inc 运算。

输出

对于每个 rmq 操作,为其写入结果。请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。

示例

输入 #1

4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

输出 #1

1
0
0