Description
小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 \(n\) 个人的队伍，选手在每支队伍内都是从 \(1\) 到 \(n\) 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 \(i\)（\(1 \leq i \leq n\)）的选手的程序设计水平为 \(a _ i\)；小 O 率领的队伍中，编号为 \(i\)（\(1 \leq i \leq n\)）的选手的程序设计水平为 \(b _ i\)。特别地，\(\{a _ i\}\) 和 \(\{b _ i\}\) 还分别构成了从 \(1\) 到 \(n\) 的排列。
每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 \(l, r\)（\(1 \leq l \leq r \leq n\)），表示这一场比赛会邀请两队中编号属于 \([l, r]\) 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 \(p, q\)（\(l \leq p \leq q \leq r\)），只有编号属于 \([p, q]\) 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 \([p, q]\) 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 \(m _ a\)，小 O 派出的选手水平为 \(m _ b\)，则比赛的精彩程度为 \(m _ a \times m _ b\)。
NOIP 总共有 \(Q\) 场比赛，每场比赛的参数 \(l, r\) 都已经确定，但是 \(p, q\) 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 \(p, q\)（\(l \leq p \leq q \leq r\)）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 \(2 ^ {64}\) 取模的结果即可。
link。
Solution
考虑把询问离线下来然后对 \(r\) 做扫描线。
设 \(x_i=\max\limits_{j=i}^{r}{a_j},y_i=\max\limits_{j=i}^{r}{b_j}\)。
那么区间 \([l_0,r_0]\) 的答案就是 \(r\) 取 \([l_0,r_0]\) 时 \(x_{l_0}\times y_{l_0}\) 的历史版本和 \(S\)。
首先可以用单调栈维护对于每个 \(r\)，他能控制 \(x\) 的范围和控制 \(y\) 的范围，所以当 \(r\) 往右移一格，只会有三种操作：
- 将区间的 \(x\) 更改为 \(a_r\)。
- 将区间的 \(y\) 更改为 \(a_r\)。
- 对于 \([1,r]\) 里的所有 \(i\)，让 \(S_i\) 加 \(x_i\times y_i\)。
最后需要多次查询区间 \(S\) 之和。
考虑用线段树维护，容易发现每次操作之后 \(S\) 的增量一定可以表示为：\(add_{x}\times X+add_y\times Y+add_{xy}\times XY+add_c\)，其中 \(add_x,add_y,add_{xy},add_c\) 都是常数。
所以可以维护懒标记 \(tag=(set_x,set_y,add_x,add_y,add_{xy},add_c)\) 分别表示区间 \(x\) 赋值标记，区间 \(y\) 赋值标记和四个系数。
考虑怎样合并两个懒标记 \(tag_1,tag_2\)。
这里需要分类讨论 \(tag_1\) 是否有 \(x\) 赋值和 \(y\) 赋值。
-
如果 \(x\) 和 \(y\) 都有赋值，那么只用更新 \(add_c\)。
-
如果 \(x\) 有，\(y\) 没有，那么可以用 \(tag_2\) 的 \(add_{xy}\) 和 \(add_y\) 更新 \(add_t\)，\(add_x\) 更新 \(add_c\)（\(x\) 没有 \(y\) 没有是同理的）。
-
如果 \(x\) 和 \(y\) 都没有，那么只要将 \(tag_2\) 的 \(add_x\) 更新 \(add_x\)，\(add_y\) 更新 \(add_y\)，\(add_{xy}\) 更新 \(add_xy\) 即可。
不要忘记 \(add_c\) 要直接合并。
时间复杂度：\(O((n+q)\log n)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
using u64 = uint64_t;
const int kMaxN = 2.5e5 + 5;
struct Node {
u64 sumx, sumy, sumxy, sum;
Node() {}
Node(u64 _sumx, u64 _sumy, u64 _sumxy, u64 _sum) : sumx(_sumx), sumy(_sumy), sumxy(_sumxy), sum(_sum) {}
friend Node operator +(Node n1, Node n2) {
return {n1.sumx + n2.sumx, n1.sumy + n2.sumy, n1.sumxy + n2.sumxy, n1.sum + n2.sum};
}
} t[kMaxN * 4];
struct Tag {
u64 setx, sety, addx, addy, addxy, addc; // x 的赋值，y 的赋值，x 对 sum 的系数，y 对 sum 的系数，xy 对 sum 的系数，常数对 sum 的系数
Tag() {}
Tag(u64 _setx, u64 _sety, u64 _addx, u64 _addy, u64 _addxy, u64 _addc) : setx(_setx), sety(_sety), addx(_addx), addy(_addy), addxy(_addxy), addc(_addc) {}
friend Tag operator +(Tag t1, Tag t2) { // t1：前面的，t2：后面的
Tag ret = t1;
if (t2.setx) ret.setx = t2.setx;
if (t2.sety) ret.sety = t2.sety;
if (t1.setx) {
ret.addc += t1.setx * t2.addx;
if (t1.sety) ret.addc += t1.sety * t2.addy + t1.setx * t1.sety * t2.addxy;
else ret.addy += t2.addy + t1.setx * t2.addxy;
} else {
ret.addx += t2.addx;
if (t1.sety) ret.addx += t1.sety * t2.addxy, ret.addc += t1.sety * t2.addy;
else ret.addy += t2.addy, ret.addxy += t2.addxy;
}
ret.addc += t2.addc;
return ret;
}
} tag[kMaxN * 4];
int n, q;
int a[kMaxN], b[kMaxN], la[kMaxN], lb[kMaxN], stka[kMaxN], stkb[kMaxN];
u64 ans[kMaxN];
std::vector<std::pair<int, int>> vec[kMaxN];
Node merge(Node a, Tag t, int len) {
Node ret = a;
if (t.setx) ret.sumx = t.setx * len;
if (t.sety) ret.sumy = t.sety * len;
if (t.setx && t.sety) ret.sumxy = t.setx * t.sety * len;
else if (t.setx) ret.sumxy = t.setx * a.sumy;
else if (t.sety) ret.sumxy = t.sety * a.sumx;
ret.sum += a.sumx * t.addx + a.sumy * t.addy + a.sumxy * t.addxy + t.addc * len;
return ret;
}
struct SGT {
Node t[kMaxN * 4];
Tag tag[kMaxN * 4];
void pushup(int x) {
t[x] = t[x << 1] + t[x << 1 | 1];
}
void addtag(int x, int l, int r, Tag tg) {
t[x] = merge(t[x], tg, r - l + 1), tag[x] = tag[x] + tg;
}
void pushdown(int x, int l, int r) {
if (!tag[x].setx && !tag[x].sety && !tag[x].addx && !tag[x].addy && !tag[x].addxy && !tag[x].addc) return;
int mid = (l + r) >> 1;
addtag(x << 1, l, mid, tag[x]), addtag(x << 1 | 1, mid + 1, r, tag[x]);
tag[x] = {0, 0, 0, 0, 0, 0};
}
void update(int x, int l, int r, int ql, int qr, Tag t) {
if (l > qr || r < ql) {
return;
} else if (l >= ql && r <= qr) {
return addtag(x, l, r, t);
}
pushdown(x, l, r);
int mid = (l + r) >> 1;
update(x << 1, l, mid, ql, qr, t), update(x << 1 | 1, mid + 1, r, ql, qr, t);
pushup(x);
}
u64 query(int x, int l, int r, int ql, int qr) {
if (l > qr || r < ql) {
return 0;
} else if (l >= ql && r <= qr) {
return t[x].sum;
}
pushdown(x, l, r);
int mid = (l + r) >> 1;
return query(x << 1, l, mid, ql, qr) + query(x << 1 | 1, mid + 1, r, ql, qr);
}
} sgt;
void dickdreamer() {
int _case;
std::cin >> _case >> n;
for (int i = 1; i <= n; ++i) std::cin >> a[i];
for (int i = 1; i <= n; ++i) std::cin >> b[i];
std::cin >> q;
for (int i = 1; i <= q; ++i) {
int l, r;
std::cin >> l >> r;
vec[r].emplace_back(l, i);
}
int topa = 0, topb = 0;
for (int i = 1; i <= n; ++i) {
for (; topa && a[stka[topa]] < a[i]; --topa) {}
for (; topb && b[stkb[topb]] < b[i]; --topb) {}
la[i] = stka[topa], lb[i] = stkb[topb];
stka[++topa] = i, stkb[++topb] = i;
sgt.update(1, 1, n, la[i] + 1, i, {a[i], 0, 0, 0, 0, 0});
sgt.update(1, 1, n, lb[i] + 1, i, {0, b[i], 0, 0, 0, 0});
sgt.update(1, 1, n, 1, i, {0, 0, 0, 0, 1, 0});
for (auto p : vec[i])
ans[p.second] = sgt.query(1, 1, n, p.first, i);
}
for (int i = 1; i <= q; ++i)
std::cout << ans[i] << '\n';
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}