[NOIP2022] 比赛
0.问题转化
首先需要转化为区间历史和问题。
具体上来讲，就是将询问离线后，扫描线维护对于 \(r\) 来说，每一个 \(l\) 的 \(\sum_{i=l}^{r}(\max_{j=l}^{i}a_j\ \cdot\ \max_{j=l}^{i}b_j)\)
那么答案就是区间和。
1.构造信息与标记
接下来就是如何维护区间历史和。
问题就在于如何构造合适的 信息(\(M\)) 与 标记(\(T\))。
\(M,T\) 应当是封闭的。
观察我们的问题，实际上就是每次 \(S\gets S+X\cdot Y\)，具体的 \(X,Y\) 显然的应当使用单调栈来维护，那么每次我们都要将一部分 \(X,\ Y\) 覆盖。
\(M\) 中的内容我们至少就需要来维护 \(S,X,Y,X\cdot Y\) 了，即 \(s, x, y, xy\)。
\(T\) 中的内容呢？我们需要 \(X,Y,X\cdot Y\) 的系数，\(X,Y\) 的覆盖标记，以及一个常数 \(A\)。即 \(ax, ay, axy, cx, cy, a\)。
2.信息与标记的合并
那么我们设每次
\[\begin{aligned} s' & = s + ax \cdot x + ay \cdot y + axy \cdot xy + a \\ x' & = \begin{cases} cx, & \text{if } cx \ne 0 \\ x, & \text{if } cx = 0 \\ \end{cases} \\ y' & = \begin{cases} cy, & \text{if } cy \ne 0 \\ y, & \text{if } cy = 0 \\ \end{cases} \end{aligned} \]2.0.信息之间的合并
信息的合并是简单的，即
msg operator + (const msg &g) const { return msg(s + g.s, x + g.x, y + g.y, xy + g.xy); }
2.1.标记与信息之间的合并
标记作用于信息也是较简单的，即
struct tag {
u64 a, cx, cy, ax, ay, axy;
// ......
msg apply(msg g, u64 len) {
g.s += g.x * ax + g.y * ay + g.xy * axy + a * len;
if (cx && cy) g.x = cx * len, g.y = cy * len, g.xy = cx * cy * len;
else if (cx) g.x = cx * len, g.xy = cx * g.y;
else if (cy) g.y = cy * len, g.xy = cy * g.x;
return g;
}
};
2.2.标记之间的合并
难点在于如何合并标记，假设是 \(T_1\) 作用到 \(T_0\) 上。
-
\(T_0.cx,T_0.cy\) 都有值：
\[\begin{aligned} &\begin{cases} s_0&=s+ax_0\cdot x+ay_0\cdot y+axy_0\cdot xy+a_0\\ s_1&=s_0+ax_1\cdot x_0+ay_1\cdot y_0+axy_1\cdot x_0y_0+a_1\\ \end{cases}\\ &s_1 = s+ax_0\cdot x+ay_0\cdot y+axy_0\cdot xy+a_0+ax_1\cdot x_0+ay_1\cdot y_0+axy_1\cdot x_0y_0+a_1\\ \end{aligned} \]观察到 \(T_0.cx,T_0.cy\) 就是 \(x_0,y_0\)，那么我们可以直接将 \(ax_1\cdot x_0+ay_1\cdot y_0+axy_1\cdot x_0y_0\) 算出来，加到常数项上。
-
只有 \(T_0.cx\) 有值：
\[\begin{aligned} &\begin{cases} s_0&=s+ax_0\cdot x+ay_0\cdot y+axy_0\cdot xy+a_0\\ s_1&=s_0+ax_1\cdot x_0+ay_1\cdot y+axy_1\cdot x_0y+a_1\\ \end{cases}\\ &\begin{aligned} s_1&=s+ax_0\cdot x+ay_0\cdot y+axy_0\cdot xy+a_0+ax_1\cdot x_0+ay_1\cdot y+axy_1\cdot x_0y+a_1\\ &=s+ax_0\cdot x+(ay_0+ay_1+axy_1\cdot x_0)\cdot y+axy_0\cdot xy+a_0+ax_1\cdot x_0+a_1 \end{aligned} \end{aligned} \]将 \(ay_0+ay_1+axy_1\cdot x_0\) 作为新的 \(ay\)，\(ax_1\cdot x_0\) 加到常数项上。
-
只有 \(T_0.cy\) 有值：
与上同理。
-
\(T_0.cx,T_0.cy\) 都没有值：
\[\begin{aligned} &\begin{cases} s_0&=s+ax_0\cdot x+ay_0\cdot y+axy_0\cdot xy+a_0\\ s_1&=s_0+ax_1\cdot x+ay_1\cdot y+axy_1\cdot xy+a_1\\ \end{cases}\\ &\begin{aligned} s_1&=s+ax_0\cdot x+ay_0\cdot y+axy_0\cdot xy+a_0+ax_1\cdot x+ay_1\cdot y+axy_1\cdot xy+a_1\\ &=s+(ax_0+ax_1)\cdot x+(ay_0+ay_1)\cdot y+(axy_0+axy_1)\cdot xy+a_0+a_1 \end{aligned} \end{aligned} \]对应的系数进行对应的修改即可。
struct tag {
u64 a, cx, cy, ax, ay, axy;
// ......
tag operator + (const tag &g) const {
tag r = *this;
r.a += g.a;
if (r.cx && r.cy) r.a += g.axy * r.cx * r.cy + g.ax * r.cx + g.ay * r.cy;
else if (r.cx) r.a += g.ax * r.cx, r.ay += g.ay + g.axy * r.cx;
else if (r.cy) r.a += g.ay * r.cy, r.ax += g.ax + g.axy * r.cy;
else r.axy += g.axy, r.ax += g.ax, r.ay += g.ay;
if (g.cx) r.cx = g.cx;
if (g.cy) r.cy = g.cy;
return r;
}
};
3.代码
剩下的做正常的线段树即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
template<typename T> inline void in(T &s) {
char c = getchar(); int f = 1; s = 0;
while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
if (f < 0) s = -s;
}
const int N = 250005, P = 1000005;
struct msg {
u64 s, x, y, xy;
msg(): s(0), x(0), y(0), xy(0) {}
msg(u64 _s, u64 _x, u64 _y, u64 _xy): s(_s), x(_x), y(_y), xy(_xy) {}
msg operator + (const msg &g) const { return msg(s + g.s, x + g.x, y + g.y, xy + g.xy); }
};
struct tag {
u64 a, cx, cy, ax, ay, axy;
tag(): a(0), cx(0), cy(0), ax(0), ay(0), axy(0) {}
tag(u64 _cx, u64 _cy, u64 _a, u64 _ax, u64 _ay, u64 _axy): a(_a), cx(_cx), cy(_cy), ax(_ax), ay(_ay), axy(_axy) {}
tag operator + (const tag &g) const {
tag r = *this;
r.a += g.a;
if (r.cx && r.cy) r.a += g.axy * r.cx * r.cy + g.ax * r.cx + g.ay * r.cy;
else if (r.cx) r.a += g.ax * r.cx, r.ay += g.ay + g.axy * r.cx;
else if (r.cy) r.a += g.ay * r.cy, r.ax += g.ax + g.axy * r.cy;
else r.axy += g.axy, r.ax += g.ax, r.ay += g.ay;
if (g.cx) r.cx = g.cx;
if (g.cy) r.cy = g.cy;
return r;
}
bool empty() { return !(a || cx || cy || ax || ay || axy); }
msg apply(msg g, u64 len) {
g.s += g.x * ax + g.y * ay + g.xy * axy + a * len;
if (cx && cy) g.x = cx * len, g.y = cy * len, g.xy = cx * cy * len;
else if (cx) g.x = cx * len, g.xy = cx * g.y;
else if (cy) g.y = cy * len, g.xy = cy * g.x;
return g;
}
};
msg m[P];
tag t[P];
void pu(int o) { m[o] = m[o << 1] + m[o << 1 | 1]; }
void down(int o, int l, int r, tag w) { m[o] = w.apply(m[o], r - l + 1), t[o] = t[o] + w; }
void pd(int o, int l, int r) {
if (t[o].empty()) return ;
int mid = (l + r) >> 1;
down(o << 1, l, mid, t[o]);
down(o << 1 | 1, mid + 1, r, t[o]);
t[o] = tag();
}
void upd(int o, int l, int r, int u, int v, tag w) {
if (u <= l && r <= v) return down(o, l, r, w);
int mid = (l + r) >> 1;
pd(o, l, r);
if (u <= mid) upd(o << 1, l, mid, u, v, w);
if (v > mid) upd(o << 1 | 1, mid + 1, r, u, v, w);
pu(o);
}
msg qry(int o, int l, int r, int u, int v) {
if (u <= l && r <= v) return m[o];
int mid = (l + r) >> 1; msg ans;
pd(o, l, r);
if (u <= mid) ans = ans + qry(o << 1, l, mid, u, v);
if (v > mid) ans = ans + qry(o << 1 | 1, mid + 1, r, u, v);
pu(o);
return ans;
}
int n, q;
u64 a[N], b[N], ans[N];
vector<pair<int, int>> que[N];
struct sta {
int h; pair<u64, int> s[N];
sta() {}
void pop(u64 x) { while (h && s[h].first <= x) --h; }
void push(u64 x, int y) { s[++h] = make_pair(x, y); }
int top() { return s[h].second; }
} A, B;
int main() {
int T; in(T);
in(n);
for (int i = 1; i <= n; ++i) in(a[i]);
for (int i = 1; i <= n; ++i) in(b[i]);
in(q);
for (int i = 1; i <= q; ++i) {
int l, r; in(l), in(r);
que[r].emplace_back(make_pair(l, i));
}
for (int i = 1; i <= n; ++i) {
A.pop(a[i]), B.pop(b[i]);
upd(1, 1, n, A.top() + 1, i, tag(a[i], 0, 0, 0, 0, 0));
upd(1, 1, n, B.top() + 1, i, tag(0, b[i], 0, 0, 0, 0));
upd(1, 1, n, 1, i, tag(0, 0, 0, 0, 0, 1));
A.push(a[i], i), B.push(b[i], i);
for (auto j : que[i]) {
int l, id; tie(l, id) = j;
ans[id] = qry(1, 1, n, l, i).s;
}
}
for (int i = 1; i <= q; ++i) printf("%llu\n", ans[i]);
return 0;
}