A. 寿命修改
知识点：线段树、摊还分析
meyi 老师锐评：这道题是最一眼的。
如果青蛙不会死，这就是道裸的线段树板子题。
考虑每个线段树结点维护三个东西：寿命和、活青蛙寿命最小值和活青蛙数量。
如果修改操作导致区间内青蛙死亡（通过最小值判断），就暴力递归到叶子结点处理。每次递归到叶子的复杂度为 。
虽然单次修改可能导致多只青蛙死亡，复杂度较高，但因为每只青蛙最多只会死一次，所以清理死青蛙的总复杂度为 。
算法的总体复杂度为 。
标程
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 200000 + 9;
constexpr ll INF = 1'000'000'000'000'000'000;
struct Node
{
int l, r;
int alive;
ll sum, min, lazy;
Node *lc, *rc;
void addlife(ll k)
{
lazy += k;
sum += k * alive;
min += k;
}
void pushdown()
{
lc->addlife(lazy);
rc->addlife(lazy);
lazy = 0;
}
void update()
{
alive = lc->alive + rc->alive;
sum = lc->sum + rc->sum;
min = std::min(lc->min, rc->min);
}
};
Node *root, pool[N * 2], *alloc = pool;
void kill(Node *x)
{
if (x->min > 0)
return;
if (x->l == x->r)
{
x->sum = 0;
x->alive = 0;
x->min = INF;
return;
}
x->pushdown();
kill(x->lc);
kill(x->rc);
x->update();
}
void change(Node *x, int l, int r, ll k)
{
if (x->l >= l && x->r <= r)
{
x->addlife(k);
kill(x);
return;
}
x->pushdown();
if (l <= x->lc->r)
change(x->lc, l, r, k);
if (r >= x->rc->l)
change(x->rc, l, r, k);
x->update();
}
ll query(Node *x, int l, int r)
{
if (x->l >= l && x->r <= r)
return x->sum;
x->pushdown();
ll res = 0;
if (l <= x->lc->r)
res += query(x->lc, l, r);
if (r >= x->rc->l)
res += query(x->rc, l, r);
return res;
}
Node *buildTree(int l, int r)
{
Node *p = alloc++;
p->l = l;
p->r = r;
p->lazy = 0;
if (l == r)
{
cin >> p->sum;
p->min = p->sum;
p->alive = 1;
p->lc = p->rc = nullptr;
return p;
}
int mid = (l + r) / 2;
p->lc = buildTree(l, mid);
p->rc = buildTree(mid + 1, r);
p->update();
return p;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
root = buildTree(1, n);
for (int i = 0; i < m; ++i)
{
int type, l, r;
cin >> type >> l >> r;
if (type == 1) // change
{
ll k;
cin >> k;
change(root, l, r, k);
}
else // query
{
cout << query(root, l, r) << '\n';
}
}
}
Java
import java.util.*;
import java.io.*;
public class Main {
static Kattio io = new Kattio();
final static int N = 200000 + 9;
static Node root;
static int n;
static int[] a = new int[N];
static Node build(int l, int r) {
Node p = new Node(l, r);
if (l == r) {
p.sum = a[l];
p.min = a[l];
p.alive = 1;
return p;
}
int mid = (l + r) / 2;
p.lc = build(l, mid);
p.rc = build(mid + 1, r);
p.update();
return p;
}
static void kill(Node p) {
if (p.min > 0) {
return;
}
if (p.l == p.r) {
p.alive = 0;
p.sum = 0;
p.min = Node.INF;
return;
}
p.pushdown();
kill(p.lc);
kill(p.rc);
p.update();
}
static void change(Node p, int l, int r, long k) {
if (p.l >= l && p.r <= r) {
p.addlife(k);
kill(p);
return;
}
p.pushdown();
if (l <= p.lc.r) {
change(p.lc, l, r, k);
}
if (r >= p.rc.l) {
change(p.rc, l, r, k);
}
p.update();
}
static long query(Node p, int l, int r) {
if (p.l >= l && p.r <= r) {
return p.sum;
}
p.pushdown();
long res = 0;
if (l <= p.lc.r) {
res += query(p.lc, l, r);
}
if (r >= p.rc.l) {
res += query(p.rc, l, r);
}
return res;
}
public static void main(String[] args) {
n = io.nextInt();
int m = io.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = io.nextInt();
}
root = build(1, n);
for (int i = 0; i < m; i++) {
int op = io.nextInt();
int l = io.nextInt();
int r = io.nextInt();
if (op == 1) {
long k = io.nextLong();
change(root, l, r, k);
} else {
io.println(query(root, l, r));
}
}
io.close();
}
}
class Node {
int l, r;
int alive;
long sum, min, lazy;
Node lc, rc;
final static long INF = 1000000000000000000L; // 10^18
Node(int l, int r) {
this.l = l;
this.r = r;
}
void addlife(long k) {
sum += k * alive;
min += k;
lazy += k;
}
void pushdown() {
if (lazy != 0) {
lc.addlife(lazy);
rc.addlife(lazy);
lazy = 0;
}
}
void update() {
sum = lc.sum + rc.sum;
min = Math.min(lc.min, rc.min);
alive = lc.alive + rc.alive;
}
}
class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// 标准 IO
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// 在没有其他输入时返回 null
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) {}
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
Python
INF = 10**18
N = 200000 + 9
s = [0] * (N * 4)
mn = [0] * (N * 4)
alive = [0] * (N * 4)
lazy = [0] * (N * 4)
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
def add_life(p: int, val: int):
s[p] += alive[p] * val
mn[p] += val
lazy[p] += val
def pushdown(p: int):
if lazy[p]:
add_life(p * 2, lazy[p])
add_life(p * 2 + 1, lazy[p])
lazy[p] = 0
def update(p: int):
s[p] = s[p * 2] + s[p * 2 + 1]
mn[p] = min(mn[p * 2], mn[p * 2 + 1])
alive[p] = alive[p * 2] + alive[p * 2 + 1]
def build(p: int, l: int, r: int):
if l == r:
s[p] = mn[p] = a[l]
alive[p] = 1
return
mid = (l + r) // 2
build(p * 2, l, mid)
build(p * 2 + 1, mid + 1, r)
update(p)
def kill(p: int, pl: int, pr: int):
if mn[p] > 0:
return
if pl == pr:
s[p] = 0
mn[p] = INF
alive[p] = 0
return
pushdown(p)
mid = (pl + pr) // 2
kill(p * 2, pl, mid)
kill(p * 2 + 1, mid + 1, pr)
update(p)
def change(p: int, pl: int, pr: int, l: int, r: int, val: int):
if l <= pl and pr <= r:
add_life(p, val)
kill(p, pl, pr)
return
pushdown(p)
mid = (pl + pr) // 2
if l <= mid:
change(p * 2, pl, mid, l, r, val)
if r > mid:
change(p * 2 + 1, mid + 1, pr, l, r, val)
update(p)
def query(p: int, pl: int, pr: int, l: int, r: int):
if l <= pl and pr <= r:
return s[p]
pushdown(p)
mid = (pl + pr) // 2
res = 0
if l <= mid:
res += query(p * 2, pl, mid, l, r)
if r > mid:
res += query(p * 2 + 1, mid + 1, pr, l, r)
return res
build(1, 1, n)
for _ in range(m):
tmp = list(map(int, input().split()))
op, l, r = tmp[0], tmp[1], tmp[2]
if op == 1: # change
k = tmp[3]
change(1, 1, n, l, r, k)
else: # query
print(query(1, 1, n, l, r))
京公网安备 11010502036488号