扫描线历史和问题
stripe_python · · 算法·理论
4-side 矩形加 & 求和
给定一个
n \times n 的二维平面,先进行n 次 4-side 矩形加,再查询n 次 4-side 矩形内部的整点和。
我们将修改矩形和查询矩形都差分成如图所示的 3-side 矩形:
对
-
在扫描到修改矩形的左边界时,我们要做一个区间加:
-
在扫描到查询矩形的右边界时,我们要做一个区间求和:
将
维护两个长为
n 的序列a_i,b_i ,支持如下操作:
- 给定
l,r,v ,对i \in [l, r] 令a_i \gets a_{i}+v 。- 对
i \in [1,n] 令b_i \gets b_i +a_i 。- 给定
l,r ,求\sum \limits_{i=l}^r b_i 。
上述定义中,
对于历史和问题,通用的做法是将信息设计为向量,标记设计为矩阵,从而信息合并是向量加法,标记合并是矩阵乘法。对于本题,我们考虑将信息设计为
- 区间加
v :\begin{bmatrix} 1 & 0 & v \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} \sum a_i \\ \sum b_i \\ \text{len} \end{bmatrix}=\begin{bmatrix} \sum (a_i+v) \\ \sum b_i \\ \text{len} \end{bmatrix} 。 - 更新历史和:
\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} \sum a_i \\ \sum b_i \\ \text{len} \end{bmatrix}=\begin{bmatrix} \sum a_i \\ \sum (a_i+b_i) \\ \text{len} \end{bmatrix} 。
直接使用矩阵会获得巨大常数。事实上,可以只维护形如
复杂度
BZOJ4262 Sum
给定一个长为
n 的序列a_i ,q 次询问给定l_1,r_1,l_2,r_2 ,查询\sum_{l \in [l_1,r_1]} \sum_{r \in [l_2,r_2]} \left(\max_{i \in [l,r]} a_i - \min_{i \in [l,r]} a_i\right)
显然一次询问的结果可以拆成
考虑每个数
这里有一个细节:
现在问题被转化成先做 4-side 矩形加,再做 4-side 矩形求和的问题,扫描线历史和解决。视
:::::info[代码]
const int N = 1e5 + 5;
int n, m, a[N], x[N], y[N]; i64 ans[N];
vector<tuple<int, int, i64>> U[N]; // (y1, y2, v)
vector<tuple<int, int, int, int>> Q[N]; // (y1, y2, type, id)
void add(int x1, int y1, int x2, int y2, i64 v) {
U[x1].emplace_back(y1, y2, v);
U[x2+1].emplace_back(y1, y2, -v);
}
void prework() {
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
x[i] = st.empty() ? 1 : st.top()+1, st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
y[i] = st.empty() ? n : st.top()-1, st.emplace(i);
}
for (int i = 1; i <= n; i++) add(x[i], i, i, y[i], a[i]);
while (!st.empty()) st.pop();
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
x[i] = st.empty() ? 1 : st.top()+1, st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] > a[i]) st.pop();
y[i] = st.empty() ? n : st.top()-1, st.emplace(i);
}
for (int i = 1; i <= n; i++) add(x[i], i, i, y[i], -a[i]);
}
using info_t = tuple<i64, i64, int>;
using tag_t = tuple<i64, i64, i64>;
const tag_t I{};
info_t operator+ (const info_t& u, const info_t& v) {
auto [a1, b1, l1] = u; auto [a2, b2, l2] = v;
return {a1 + a2, b1 + b2, l1 + l2};
}
tag_t operator* (const tag_t& u, const tag_t& v) {
auto [x1, y1, z1] = u; auto [x2, y2, z2] = v;
return {x1 + x2, y1 + y2, y1 * x2 + z1 + z2};
}
info_t operator* (const tag_t& u, const info_t& v) {
auto [x, y, z] = u; auto [a, b, l] = v;
return {a + x * l, y * a + b + z * l, l};
}
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
info_t val[N << 2];
tag_t tag[N << 2];
void pushup(int rt) {val[rt] = val[ls] + val[rs];}
void apply(int rt, const tag_t& c) {val[rt] = c * val[rt], tag[rt] = c * tag[rt];}
void pushdown(int rt) {
if (tag[rt] == I) return;
apply(ls, tag[rt]), apply(rs, tag[rt]), tag[rt] = I;
}
void build(int l = 1, int r = n, int rt = 1) {
if (l == r) return val[rt] = info_t(0, 0, 1), void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}
void update(int tl, int tr, const tag_t& c, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return apply(rt, c), void();
int mid = (l + r) >> 1; pushdown(rt);
if (tl <= mid) update(tl, tr, c, l, mid, ls);
if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
info_t ask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return val[rt];
int mid = (l + r) >> 1; pushdown(rt);
if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
}
} T;
void _main() {
prework(); cin >> m;
for (int i = 1, l1, r1, l2, r2; i <= m; i++) {
cin >> l1 >> r1 >> l2 >> r2;
Q[r1].emplace_back(l2, r2, 1, i);
if (l1 > 1) Q[l1-1].emplace_back(l2, r2, -1, i);
}
T.build();
for (int x = 1; x <= n; x++) {
for (auto [l, r, v] : U[x]) T.update(l, r, info_t(v, 0, 0)); // op 1 += v
T.update(1, n, info_t(0, 1, 0)); // op 2
for (auto [l, r, t, id] : Q[x]) ans[id] += $1(T.ask(l, r)) * t;
}
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
:::::
P8868 [NOIP2022] 比赛
给定长为
n 的序列a_i,b_i ,q 次询问给定x,y ,查询\left(\sum_{[l,r] \subseteq [x,y]} \left(\max_{i \in [l, r]} a_i\right) \times \left(\max_{i \in [l, r]} b_i\right)\right) \bmod 2^{64}
对
考察每对
对
- 若
[l, r] \subseteq [u_r, r] ,f_l 变为a_r 。 - 若
l<u_r ,f_l 不变。
对数组
考虑在位置
上图展示了这个做法的几何意义,我们用若干垂直线拼出询问的三角形,这些垂直线段就是历史和。
至此转化为如下数据结构问题:
维护三个长为
n 的序列a_i,b_i,c_i ,支持如下操作:
- 给定
l,r,v ,对i \in [l,r] 令a_i \gets v 。- 给定
l,r,v ,对i \in [l,r] 令b_i \gets v 。- 对
i \in [1,n] 令c_i \gets c_i+a_i\times b_i 。- 给定
l,r 查询\sum \limits_{i=l}^r c_i 。
容易发现
将信息构造为向量
- 序列
a_i 赋值v :\begin{bmatrix} 0 & 0 & 0 & 0 & v \\ 0 & 1 & 0 & 0 & 0 \\ 0 & v & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \sum a_i \\ \sum b_i \\ \sum a_ib_i \\ \sum c_i \\ \text{len} \end{bmatrix}=\begin{bmatrix} \sum v \\ \sum b_i \\ \sum vb_i \\ \sum c_i \\ \text{len} \end{bmatrix} 。 - 序列
b_i 赋值v :\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & v \\ v & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \sum a_i \\ \sum b_i \\ \sum a_ib_i \\ \sum c_i \\ \text{len} \end{bmatrix}=\begin{bmatrix} \sum a_i \\ \sum v \\ \sum va_i \\ \sum c_i \\ \text{len} \end{bmatrix} 。 - 更新历史和:
\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \sum a_i \\ \sum b_i \\ \sum a_ib_i \\ \sum c_i \\ \text{len} \end{bmatrix}=\begin{bmatrix} \sum a_i \\ \sum b_i \\ \sum a_ib_i \\ \sum c_i+\sum a_ib_i \\ \text{len} \end{bmatrix} 。
进行半群优化。观察复合后的矩阵结构,考虑只维护形如
视
:::::info[代码]
const int N = 2.5e5 + 5;
int n, m, a[N], b[N], la[N], lb[N]; u64 ans[N];
vector<pair<int, int>> Q[N]; // (l, id)
void prework() {
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
la[i] = st.empty() ? 1 : st.top()+1, st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = 1; i <= n; i++) {
while (!st.empty() && b[st.top()] < b[i]) st.pop();
lb[i] = st.empty() ? 1 : st.top()+1, st.emplace(i);
}
}
using info_t = tuple<u64, u64, u64, u64, u64>;
using tag_t = tuple<u64, u64, u64, u64, u64, u64, u64, u64, u64, u64, u64, u64>;
const tag_t I(1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0);
info_t operator+ (const info_t& u, const info_t& v) {
auto [a1, b1, ab1, c1, l1] = u;
auto [a2, b2, ab2, c2, l2] = v;
return {a1 + a2, b1 + b2, ab1 + ab2, c1 + c2, l1 + l2};
}
tag_t operator* (const tag_t& u, const tag_t& v) {
auto [a00, a04, a11, a14, a20, a21, a22, a24, a30, a31, a32, a34] = u;
auto [b00, b04, b11, b14, b20, b21, b22, b24, b30, b31, b32, b34] = v;
return {
a00 * b00,
a00 * b04 + a04,
a11 * b11,
a11 * b14 + a14,
a20 * b00 + a22 * b20,
a21 * b11 + a22 * b21,
a22 * b22,
a20 * b04 + a21 * b14 + a22 * b24 + a24,
a30 * b00 + a32 * b20 + b30,
a31 * b11 + a32 * b21 + b31,
a32 * b22 + b32,
a30 * b04 + a31 * b14 + a32 * b24 + a34 + b34
};
}
info_t operator* (const tag_t& u, const info_t& v) {
auto [a00, a04, a11, a14, a20, a21, a22, a24, a30, a31, a32, a34] = u;
auto [a, b, ab, c, l] = v;
return {
a00 * a + a04 * l,
a11 * b + a14 * l,
a20 * a + a21 * b + a22 * ab + a24 * l,
a30 * a + a31 * b + a32 * ab + c + a34 * l,
l
};
}
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
info_t val[N << 2];
tag_t tag[N << 2];
void pushup(int rt) {val[rt] = val[ls] + val[rs];}
void apply(int rt, const tag_t& c) {val[rt] = c * val[rt], tag[rt] = c * tag[rt];}
void pushdown(int rt) {
if (tag[rt] == I) return;
apply(ls, tag[rt]), apply(rs, tag[rt]), tag[rt] = I;
}
void build(int l = 1, int r = n, int rt = 1) {
if (l == r) return val[rt] = info_t(0, 0, 0, 0, 1), void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}
void update(int tl, int tr, const tag_t& c, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return apply(rt, c), void();
int mid = (l + r) >> 1; pushdown(rt);
if (tl <= mid) update(tl, tr, c, l, mid, ls);
if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
info_t ask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return val[rt];
int mid = (l + r) >> 1; pushdown(rt);
if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
}
} T;
void _main() {
cin >> n >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
prework(), cin >> m;
for (int i = 1, l, r; i <= m; i++) {
cin >> l >> r;
Q[r].emplace_back(l, i);
}
T.build();
for (int r = 1; r <= n; r++) {
T.update(la[r], r, tag_t(0, a[r], 1, 0, 0, a[r], 0, 0, 0, 0, 0, 0)); // op 1
T.update(lb[r], r, tag_t(1, 0, 0, b[r], b[r], 0, 0, 0, 0, 0, 0, 0)); // op 2
T.update(1, n, tag_t(1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0)); // op 3
for (auto [l, id] : Q[r]) ans[id] += $3(T.ask(l, r));
}
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
:::::