原题链接：http://ac.jobdu.com/problem.php?pid=1407
线段树，区间更新，查询区间最小值。
注意区间更新,查询的时候，区间$\begin{align*}[L,R] \end{align*}$$\begin{align*}L \end{align*}$都可能大于$\begin{align*}R\end{align*}$。。
有个地方写sb了害的我wa了好几次%>_<%。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define lc root<<1
#define rc root<<1|1
#define mid ((l+r)>>1)
using std::min;
const int Max_N = ;
const int INF = ~0u >> ;
struct Node {
int val, add;
};
struct SegTree {
Node seg[Max_N << ];
inline void push_up(int root) {
seg[root].val = min(seg[lc].val, seg[rc].val);
}
inline void built(int root, int l, int r) {
seg[root].add = ;
if (l == r) {
scanf("%d", &seg[root].val);
return;
}
built(lc, l, mid);
built(rc, mid + , r);
push_up(root);
}
inline void push_down(int root) {
if (seg[root].add != ) {
int &_add = seg[root].add;
seg[lc].add += _add;
seg[lc].val += _add;
seg[rc].add += _add;
seg[rc].val += _add;
_add = ;
}
}
inline void update(int root, int l, int r, int x, int y, int v) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
seg[root].add += v;
seg[root].val += v;
return;
}
push_down(root);
update(lc, l, mid, x, y, v);
update(rc, mid + , r, x, y, v);
push_up(root);
}
inline int query(int root, int l, int r, int x, int y) {
if (x > r || y < l) return INF;
if (x <= l && y >= r) return seg[root].val;
push_down(root);
int v1 = query(lc, l, mid, x, y);
int v2 = query(rc, mid + , r, x, y);
return min(v1, v2);
}
}seg;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
char buf[];
int n, m, a, b, c;
while (~scanf("%d", &n)) {
seg.built(, , n);
scanf("%d\n", &m);
while (m--) {
gets(buf);
char *p = strchr(buf, ' ');
if (strchr(++p, ' ')) {
sscanf(buf, "%d %d %d", &a, &b, &c);
if (a <= b) {
seg.update(, , n, ++a, ++b, c);
} else {
seg.update(, , n, ++a, n, c);
seg.update(, , n, , ++b, c);
}
} else {
sscanf(buf, "%d %d", &a, &b);
if (a <= b) {
printf("%d\n", seg.query(, , n, ++a, ++b));
} else {
int v1 = seg.query(, , n, ++a, n);
int v2 = seg.query(, , n, , ++b);
printf("%d\n", min(v1, v2));
}
}
}
}
return ;
}