Circular RMQ

题面翻译

【题目大意】

给定一个环形数列 $a_0,a_1,\dots,a_{n-1}$。

现在有 $2$ 种操作：

• $\operatorname{inc}(lf,rg,v)$：将区间 $[lf,rg]$ 中的每个数增加 $v$。
• $\operatorname{rmq}(lf,rg)$：求出区间 $[lf,rg]$ 中的最小值。

因为数列是环形的，所以当 $n=5$，$lf=3$，$rg=1$ 时，表示的区间下标为 $3,4,0,1$。

Translated by 小恐。

【输入】

第一行有一个整数 $n$。

第二行为数列的初始状态 $a_0,a_1,\dots,a_{n-1}$，$a_i$ 是整数。

第三行有一个整数 $m$，表示操作次数。

接下来m行每行为一个操作。如果该行有两个整数 $lf$，$rg$ 表示 $\operatorname{rmq}$ 操作，如果该行有三个整数 $lf$，$rg$，$v$ 表示 $\operatorname{inc}$ 操作。

【输出】

对于每个 $\operatorname{rmq}$ 操作输出一行答案。

题目描述

You are given circular array $a_{0},a_{1},...,a_{n-1}$ . There are two types of operations with it:

• $inc(lf,rg,v)$ — this operation increases each element on the segment $[lf,rg]$ (inclusively) by $v$ ;
• $rmq(lf,rg)$ — this operation returns minimal value on the segment $[lf,rg]$ (inclusively).

Assume segments to be circular, so if $n=5$ and $lf=3,rg=1$ , it means the index sequence: $3,4,0,1$ .

Write program to process given sequence of operations.

输入格式

The first line contains integer $n$ ( $1<=n<=200000$ ). The next line contains initial state of the array: $a_{0},a_{1},...,a_{n-1}$ ( $-10^{6}<=a_{i}<=10^{6}$ ), $a_{i}$ are integer. The third line contains integer $m$ ( $0<=m<=200000$ ), $m$ — the number of operartons. Next $m$ lines contain one operation each. If line contains two integer $lf,rg$ ( $0<=lf,rg<=n-1$ ) it means $rmq$ operation, it contains three integers $lf,rg,v$ ( $0<=lf,rg<=n-1;-10^{6}<=v<=10^{6}$ ) — $inc$ operation.

输出格式

For each $rmq$ operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

样例 #1

样例输入 #1

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

样例输出 #1

1
0
0