题目大意
给你一个环形数列,完成环形数列上区间加法和区间求最小值。
分析
算是一道比较水的线段树模板题。
如果l>r的话,那么修改l,n和1,r区间。
不然的话那么就修改l,r区间。
其他的基础操作可以看我的随笔:【传送门】
还要注意开long long
。
ac代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 200005
#define ll long long
#define linf 9223372036854775807
using namespace std;
ll a[N];
bool bo;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1;
bo = 0;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') fl = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
if (ch == ' ') bo = 1;
x *= fl;
}
struct segment_tree {
#define lc (nod << 1)
#define rc (nod << 1 | 1)
#define mid ((l + r) >> 1)
struct node {
ll mn, tag;
int l, r;
node() {
mn = l = r = tag;
}
}tr[N << 2];
void pushup(int nod) {
tr[nod].mn = min(tr[lc].mn, tr[rc].mn);
}
void pushdown(int nod) {
if (tr[nod].tag == 0 || tr[nod].l == tr[nod].r) return;
ll tmp = tr[nod].tag;
tr[nod].tag = 0;
tr[lc].mn += tmp;
tr[rc].mn += tmp;
tr[lc].tag += tmp;
tr[rc].tag += tmp;
}
void build(int l, int r, int nod, ll *a) {
tr[nod].l = l, tr[nod].r = r;
if (l == r) {
tr[nod].mn = a[l];
return;
}
build(l, mid, lc, a);
build(mid + 1, r, rc, a);
pushup(nod);
}
void update_sec(int ql, int qr, int nod, ll val) {
int l = tr[nod].l, r = tr[nod].r;
pushdown(nod);
if (ql <= l && r <= qr) {
tr[nod].mn += val;
tr[nod].tag += val;
return;
}
if (ql <= mid) update_sec(ql, qr, lc, val);
if (qr > mid) update_sec(ql, qr, rc, val);
pushup(nod);
}
ll query_sec_min(int ql, int qr, int nod) {
int l = tr[nod].l, r = tr[nod].r;
pushdown(nod);
if (ql <= l && r <= qr) return tr[nod].mn;
ll res = linf;
if (ql <= mid) res = min(res, query_sec_min(ql, qr, lc));
if (qr > mid) res = min(res, query_sec_min(ql, qr, rc));
return res;
}
}tr;
int n, m;
int main() {
read(n);
for (int i = 1; i <= n; i ++) read(a[i]);
tr.build(1, n, 1, a);
read(m);
while (m --) {
int l, r;
read(l); read(r);
l ++; r ++;
if (!bo) {
ll res = linf;
if (l > r) {
res = min(res, tr.query_sec_min(l, n, 1));
res = min(res, tr.query_sec_min(1, r, 1));
}
else res = min(res, tr.query_sec_min(l, r, 1));
printf("%lld\n", res);
}
else {
ll x;
cin>> x;
if (l > r) {
tr.update_sec(l, n, 1, x);
tr.update_sec(1, r, 1, x);
}
else tr.update_sec(l, r, 1, x);
}
}
return 0;
}