2022 05 08 线段树
| POJ2828-Buy Tickets | 提高 | http://poj.org/problem?id=2828 |
|---|---|---|
| Ray,Pass me the Dishes, UVa1400 | 提高 | https://www.luogu.com.cn/problem/UVA1400 |
| POJ3468 A Simple Problem with Integers | 提高 | http://poj.org/problem?id=3468 |
| USACO13Jan G, P3. Seating | 提高 | https://www.luogu.com.cn/problem/P3071 |
| 维护序列(AHOI 2009) | 提高 | https://www.luogu.com.cn/problem/P2023 |
| USACO 2013 Dec G. Optimal Milking | 提高+ | https://www.luogu.com.cn/problem/P3097 |
Buy Tickets¶
/**
* @file poj/2828/segment_tree.cpp
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief 有一个空的序列，有 n 个人要插队，第 i 个人有一个 id，
* 这个人插入队列要排在 pos[i] 个人后面。
* 最后从队首开始输出每个人的 id。
*
* 逆向思维，把插队问题改成出列问题，for i from n to 1,
* 每个排在 pos[i] + 1 上的人出队，存下这个出队者的 id。
* @version 1.0
* @date 2022-05-06
*
* @copyright Copyright (c) 2022
*
**/
#include <iostream>
const int N = 200000 + 10;
int n;
int Pos[N], Val[N], Ans[N];
#define ls (rt << 1)
#define rs (rt << 1 | 1)
struct SegTree {
int sum[4 * N];
/**
* @brief 使用子节点的信息更新父节点的信息
*
* @param rt 根节点
**/
void maintain(int rt) { sum[rt] = sum[ls] + sum[rs]; }
/**
* @brief 建立以 rt 为根节点，管理[l, r]的线段树
*
* @param rt 线段树的根节点
* @param l 根节点 rt 管理的左短点
* @param r 根节点 rt 管理的右端点
**/
void build(int rt, int l, int r) {
if (l == r) {
sum[rt] = 1;
return;
} else {
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
maintain(rt);
}
}
/**
* @brief 在以 rt 为根的树上，包括原序列上[l, r]这一段，记录 pos 位置上的人为
*val
*
* @param rt 管理这一段的线段树的树根
* @param l 这一段在原序列中的左端点
* @param r 这一段在原序列中的右端点
* @param pos 被改变的点的位置
* @param val 该点被改变之后的值
**/
void update(int rt, int l, int r, int pos, int val) {
if (l == r) {
Ans[l] = val;
sum[rt] = 0; // 已经走到叶节点
return;
}
int mid = l + r >> 1;
if (sum[ls] >= pos)
update(ls, l, mid, pos, val);
else
update(rs, mid + 1, r, pos - sum[ls], val);
maintain(rt); // 非叶子节点，需要调用
}
} ST;
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
while (cin >> n && n) {
ST.build(1, 1, n);
for (int i = 1; i <= n; ++i) {
cin >> Pos[i] >> Val[i];
}
for (int i = n; i >= 1; --i) {
ST.update(1, 1, n, Pos[i] + 1, Val[i]);
}
for (int i = 1; i <= n; ++i) cout << Ans[i] << ' ';
cout << endl;
}
}Ray, Pass me the Dishes!¶
用课件里的题解过的，不太会改
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
typedef long long LL;
typedef pair<int, int> Interval;
const int MAXN = 5e5 + 4;
LL SD[MAXN];
inline LL sum(int L, int R) { // [L,R]
// assert(L <= R);
return SD[R] - SD[L - 1];
}
inline LL sum(const Interval& i) { return sum(i.first, i.second); }
inline Interval maxI(const Interval& i1, const Interval& i2) {
LL s1 = sum(i1), s2 = sum(i2);
if (s1 != s2) return s1 > s2 ? i1 : i2;
return min(i1, i2);
}
struct MaxVal {
int pfx, sfx;
Interval sub;
};
struct IntervalTree {
MaxVal Nodes[MAXN * 2];
int qL, qR, N;
void build(int N) { // [1, N]
this->N = N;
build(1, N, 1);
}
void build(int L, int R, int O) {
assert(L <= R);
assert(O > 0);
if (L == R) {
Nodes[O] = {L, L, make_pair(L, L)};
return;
}
int M = (L + R) / 2, lc = 2 * O, rc = 2 * O + 1;
build(L, M, lc), build(M + 1, R, rc);
const MaxVal &nl = Nodes[lc], &nr = Nodes[rc];
MaxVal& no = Nodes[O];
no.pfx = sum(L, nl.pfx) >= sum(L, nr.pfx) ? nl.pfx : nr.pfx;
no.sfx = sum(nl.sfx, R) >= sum(nr.sfx, R) ? nl.sfx : nr.sfx;
no.sub = maxI(nl.sub, nr.sub);
no.sub = maxI(no.sub, make_pair(nl.sfx, nr.pfx));
}
Interval query(int l, int r) { // max sub [a,b] in [l, r]
assert(l <= r);
qL = l, qR = r;
return _query(1, N, 1);
}
Interval _query(const int L, const int R, const int O) {
if (qL <= L && R <= qR) return Nodes[O].sub;
int M = (L + R) / 2, lc = O * 2, rc = 2 * O + 1;
if (qR <= M) return _query(L, M, lc);
if (qL > M) return _query(M + 1, R, rc);
Interval ans = make_pair(_querySfx(L, M, lc), _queryPfx(M + 1, R, rc));
ans = maxI(ans, maxI(_query(L, M, lc), _query(M + 1, R, rc)));
return ans;
}
int _queryPfx(const int L, const int R, const int O) {
if (qL <= L && R <= qR) return Nodes[O].pfx;
int M = (L + R) / 2, lc = 2 * O, rc = 2 * O + 1;
if (qR <= M) return _queryPfx(L, M, lc);
if (qL > M) return _queryPfx(M + 1, R, rc);
int m1 = _queryPfx(L, M, lc), m2 = _queryPfx(M + 1, R, rc);
return sum(L, m1) >= sum(L, m2) ? m1 : m2;
}
int _querySfx(const int L, const int R, const int O) {
if (qL <= L && R <= qR) return Nodes[O].sfx;
int M = (L + R) / 2, lc = O * 2, rc = 2 * O + 1;
if (qR <= M) return _querySfx(L, M, lc);
if (qL > M) return _querySfx(M + 1, R, rc);
int m1 = _querySfx(L, M, lc), m2 = _querySfx(M + 1, R, rc);
return sum(m1, R) >= sum(m2, R) ? m1 : m2;
}
};
IntervalTree tree;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
SD[0] = 0;
for (int t = 1, d, a, b, N, M; cin >> N >> M; t++) {
_rep(i, 1, N) cin >> d, SD[i] = SD[i - 1] + d;
tree.build(N);
printf("Case %d:\n", t);
_rep(i, 1, M) {
cin >> a >> b;
Interval ans = tree.query(a, b);
printf("%d %d\n", ans.first, ans.second);
}
}
return 0;
}A Simple Problem with Integers¶
/**
* @file poj/3468
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief 区间修改，区间查询，带懒标记
* @see https://www.acwing.com/problem/content/244/
* @version 1.0
* @date 2022-05-06
*
* @copyright Copyright (c) 2022
*
**/
#include <cstdio>
using namespace std;
const int N = 100000 + 10;
#define mid (l + r >> 1)
#define ls (rt << 1)
#define rs (rt << 1 | 1)
typedef long long ll;
struct SegTree {
ll sum[N * 4], // sum[rt] 表示以 rt 为根的树管辖范围之和
lazy_add[N * 4]; // lazy_add[rt] 表示 rt 管辖的范围中每个元素都增加了多少
/**
* @brief 以 rt 为根节点的线段树用子节点的信息更新自己
*
* @param rt 根节点
**/
void maintain(int rt) { sum[rt] = sum[ls] + sum[rs]; }
/**
* @brief 下放延迟标记，把lazy_add下放至两棵子树，同时更新子树的sum
*
* @param rt 根节点
* @param l rt 管辖范围的左边界
* @param r rt 管辖范围的右边界
**/
void pushdown(int rt, int l, int r) {
ll &a = lazy_add[rt];
if (a == 0) return;
lazy_add[ls] += a, lazy_add[rs] += a; // 下面压力来到了左右子节点上
sum[ls] += a * (mid - l + 1), sum[rs] += a * (r - mid);
a = 0; // 清掉 rt 的标记
}
void build(int rt, int l, int r) {
lazy_add[rt] = 0;
if (l == r) {
// 建树同时读入，因为建树时建到子节点的顺序是从 1 到 n 的
scanf("%lld", &sum[rt]);
return;
}
build(ls, l, mid), build(rs, mid + 1, r);
maintain(rt);
}
/**
* @brief 改
*
* @param rt 修改的根节点
* @param val 被改成的值
* @param ql 询问区间的左端点
* @param qr 询问区间的右端点
* @param l 该根节点控制区间的左端点
* @param r 该根节点控制区间的右端点
**/
void update(int rt, ll val, int ql, int qr, int l, int r) {
if (ql <= l && r <= qr) { // rt 区间完全被询问 [L, R] 覆盖
// 进行整个区间的更新
lazy_add[rt] += val;
sum[rt] += val * (r - l + 1);
return;
}
// 非完整区间更新
pushdown(rt, l, r);
if (ql <= mid) {
update(ls, val, ql, qr, l, mid);
}
if (qr >= mid + 1) {
update(rs, val, ql, qr, mid + 1, r);
}
maintain(rt);
}
/**
* @brief 查
*
* @param rt 修改的根节点
* @param ql 询问区间的左端点
* @param qr 询问区间的右端点
* @param l 该根节点控制区间的左端点
* @param r 该根节点控制区间的右端点
**/
ll query(int rt, int ql, int qr, int l, int r) {
if (ql <= l && r <= qr) return sum[rt]; // rt 区间完全被询问 [L, R] 覆盖
pushdown(rt, l, r);
ll ans = 0;
if (ql <= mid) ans += query(ls, ql, qr, l, mid);
if (qr >= mid + 1) ans += query(rs, ql, qr, mid + 1, r);
return ans;
}
} ST;
int main() {
int n, m;
scanf("%d%d", &n, &m);
ST.build(1, 1, n);
char s[2];
for (int a, b, c; m--;) {
scanf("%s%d%d", s, &a, &b);
if (*s == 'Q') {
printf("%lld\n", ST.query(1, a, b, 1, n));
} else {
scanf("%d", &c);
ST.update(1, c, a, b, 1, n);
}
}
}Seating¶
自己做没做出来，怎么调都没有调对……把课件里代码敲了一遍
#include <bits/stdc++.h>
const int NN = 5e5 + 4;
using namespace std;
int opv[NN * 4], pfx[NN * 4], sfx[NN * 4], len[NN * 4];
void maintain(int o, int lLen, int rLen) {
int lc = 2 * o, rc = 2 * o + 1;
pfx[o] = pfx[lc] == lLen ? lLen + pfx[rc] : pfx[lc];
sfx[o] = sfx[rc] == rLen ? rLen + sfx[lc] : sfx[rc];
len[o] = max(max(len[lc], len[rc]), pfx[rc] + sfx[lc]);
}
void push_down(int o, int lLen, int rLen) {
int &op = opv[o];
if (!op || !lLen || !rLen) return;
int lc = 2 * o, rc = 2 * o + 1;
len[lc] = pfx[lc] = sfx[lc] = (op == 2 ? lLen : 0);
len[rc] = pfx[rc] = sfx[rc] = (op == 2 ? rLen : 0);
opv[lc] = opv[rc] = op, op = 0;
}
int query(int o, int L, int R, int v) {
// 在 o[L,R]中查找长度为q的连续0区间
int lc = 2 * o, rc = 2 * o + 1, m = L + (R - L) / 2;
push_down(o, m - L + 1, R - m);
if (len[lc] >= v) return query(lc, L, m, v); // 去左半边找
if (pfx[rc] + sfx[lc] >= v) return m - sfx[lc] + 1; // 横跨中间线
return query(rc, m + 1, R, v); // 去右边找
}
void update(int qL, int qR, int op, int o, int L, int R) {
int lc = 2 * o, rc = 2 * o + 1, m = L + (R - L) / 2;
if (qL <= L && qR >= R) {
len[o] = pfx[o] = sfx[o] = (op == 2 ? R - L + 1 : 0);
opv[o] = op;
return;
}
push_down(o, m - L + 1, R - m);
if (qL <= m) update(qL, qR, op, lc, L, m);
if (qR > m) update(qL, qR, op, rc, m + 1, R);
maintain(o, m - L + 1, R - m);
}
void build(int o, int L, int R) {
int lc = 2 * o, rc = 2 * o + 1, m = L + (R - L) / 2;
len[o] = pfx[o] = sfx[o] = R - L + 1;
if (L < R) build(lc, L, m), build(rc, m + 1, R);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, m, ans = 0;
char op;
cin >> n >> m, build(1, 1, n);
for (int i = 0, a, b; i < m; i++) {
cin >> op >> a;
if (op == 'A') {
if (len[1] < a)
ans++;
else {
int x = query(1, 1, n, a);
update(x, x + a - 1, 1, 1, 1, n);
}
} else
cin >> b, update(a, b, 2, 1, 1, n);
}
cout << ans << endl;
}
维护序列¶
/**
* @file luogu/2023/main.cpp
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief 区间加，区间乘，询问区间和
*
* 带懒标记的线段树
*
* 注意：因为乘的运算级别比加高，所以在做加法是不用管乘法，在做乘法时要管加法。
*
* @version 1.0
* @date 2022-05-07
*
* @copyright Copyright (c) 2022
*
**/
#include <bits/stdc++.h>
using namespace std;
const int N = 200007;
typedef long long ll;
int n, q, L, R, op;
ll k, P, a[N];
struct SegTree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid (l + r >> 1)
ll sum[N << 2], mul[N << 2], add[N << 2];
void pushdown(int rt, int l, int r) {
if (mul[rt] == 1 && add == 0) {
return; // 没有标记
}
if (l != r) {
mul[ls] = mul[ls] * mul[rt] % P;
mul[rs] = mul[rs] * mul[rt] % P;
add[ls] = (add[ls] * mul[rt] % P + add[rt]) % P;
add[rs] = (add[rs] * mul[rt] % P + add[rt]) % P;
}
sum[rt] = (sum[rt] * mul[rt] % P + add[rt] * (r - l + 1) % P) % P;
mul[rt] = 1, add[rt] = 0;
}
void pushup(int rt) { sum[rt] = sum[ls] + sum[rs]; }
void build(int rt, int l, int r) {
mul[rt] = 1, add[rt] = 0;
if (l == r) {
sum[rt] = a[l];
return;
}
build(ls, l, mid), build(rs, mid + 1, r);
pushup(rt);
}
ll query_sum(int rt, int l, int r) {
pushdown(rt, l, r);
if (L <= l && r <= R) {
return sum[rt];
}
ll ret = 0;
if (L <= mid) ret = (ret + query_sum(ls, l, mid)) % P;
if (R >= mid + 1) ret = (ret + query_sum(rs, mid + 1, r)) % P;
return ret;
}
void range_add(int rt, int l, int r) {
pushdown(rt, l, r);
if (L <= l && r <= R) {
add[rt] = (add[rt] + k) % P;
return;
}
if (L <= mid) range_add(ls, l, mid);
if (R >= mid + 1) range_add(rs, mid + 1, r);
pushdown(ls, l, mid), pushdown(rs, mid + 1, r);
pushup(rt);
}
void range_mul(int rt, int l, int r) {
pushdown(rt, l, r);
if (L <= l && r <= R) {
// 加法和乘法都要乘一个 k
mul[rt] = mul[rt] * k % P;
add[rt] = add[rt] * k % P;
return;
}
if (L <= mid) range_mul(ls, l, mid);
if (R >= mid + 1) range_mul(rs, mid + 1, r);
pushdown(ls, l, mid), pushdown(rs, mid + 1, r);
pushup(rt);
}
#undef mid
#undef ls
#undef rs
} ST;
int main() {
cin >> n >> P;
for (int i = 1; i <= n; ++i) cin >> a[i];
ST.build(1, 1, n);
int tc;
cin >> tc;
while (tc--) {
cin >> op;
if (op == 1) {
cin >> L >> R >> k;
ST.range_mul(1, 1, n);
} else if (op == 2) {
cin >> L >> R >> k;
ST.range_add(1, 1, n);
} else {
cin >> L >> R;
cout << ST.query_sum(1, 1, n) << endl;
}
}
}Optimal Milking¶
看不太懂了，好像是要维护总体、不含左端点、不含右端点、不含两个端点四种情况
#include <bits/stdc++.h>
#define N 50010
#define lson (o << 1)
#define rson (o << 1 | 1)
using namespace std;
typedef long long ll;
int f[N << 2][4], n, m;
ll ans = 0;
inline int read() {
int f = 1, x = 0;
char ch;
do {
ch = getchar();
if (ch == '-') f = -1;
} while (ch < '0' || ch > '9');
do {
x = x * 10 + ch - '0';
ch = getchar();
} while (ch >= '0' && ch <= '9');
return f * x;
}
inline int max(int a, int b, int c) { return max(max(a, b), c); }
inline int max(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); }
inline void pushup(int o) {
for (int i = 0; i < 4; i++)
f[o][i] = max(f[lson][i & 2] + f[rson][2 + (i & 1)],
f[lson][(i & 2) + 0] + f[rson][i & 1],
f[lson][(i & 2) + 1] + f[rson][i & 1]);
}
void build(int o, int l, int r) {
if (l == r) {
f[o][3] = read();
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(o);
}
void change(int o, int l, int r, int q, int v) {
if (l == r) {
f[o][3] = v;
return;
}
int mid = (l + r) >> 1;
if (q <= mid)
change(lson, l, mid, q, v);
else
change(rson, mid + 1, r, q, v);
pushup(o);
}
int main() {
n = read();
m = read();
build(1, 1, n);
while (m--) {
int x = read(), y = read();
change(1, 1, n, x, y);
ans += max(f[1][0], f[1][1], f[1][2], f[1][3]);
}
cout << ans << endl;
}