P3130 Counting Haybale P
'P' l r k
,区间加'M' l r
,求区间最小值'S' l r
,求区间和
Same Problem
Circular RMQ - 洛谷 | 计算机科学教育新生态
Solution
线段树
主要是求区间最小值。
#define lc u<<1
#define rc u<<1|1
int a[200010];
struct Tree { //线段树
ll l, r, sum, add, min;
}tr[800010];
void pushup(ll u) { //上传
tr[u].sum = tr[lc].sum + tr[rc].sum;
tr[u].min = min(tr[lc].min, tr[rc].min);
}
void pushdown(ll u) { //下传
if (tr[u].add) {
tr[lc].sum += tr[u].add * (tr[lc].r - tr[lc].l + 1);
tr[rc].sum += tr[u].add * (tr[rc].r - tr[rc].l + 1);
tr[lc].add += tr[u].add;
tr[rc].add += tr[u].add;
tr[lc].min += tr[u].add;
tr[rc].min += tr[u].add;
tr[u].add = 0;
}
}
void build(ll u, ll l, ll r) { //建树
tr[u] = {l,r,a[l],0,a[l]};
if (l == r) return;
ll m = l + r >> 1;
build(lc, l, m);
build(rc, m + 1, r);
pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
tr[u].add += k;
tr[u].min += k;
return;
}
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= m) change(lc, l, r, k);
if (r > m) change(rc, l, r, k);
pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
ll sum = 0;
if (l <= m) sum += query(lc, l, r);
if (r > m) sum += query(rc, l, r);
return sum;
}
ll querymin(ll u, ll l, ll r) { //区查
if (l <= tr[u].l && tr[u].r <= r) return tr[u].min;
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
ll ans = INTMAX_MAX;
if (l <= m) ans = min(ans, querymin(lc, l, r));
if (r > m) ans = min(ans, querymin(rc, l, r));
return ans;
}
void solve() {
int n, m;cin >> n >> m;
for (int i = 1;i <= n;i++)cin >> a[i];
build(1, 1, n);
while (m--) {
char op;cin >> op;
int l, r;cin >> l >> r;
if (op == 'P') {
int k;cin >> k;change(1, l, r, k);
} else if (op == 'M') {
cout << querymin(1, l, r) << '\n';
} else {
cout << query(1, l, r) << "\n";
}
}
}