主要写一写标记的推导。
理论大概在 关于线段树上的一些进阶操作
回忆一下普通历史和。
是对两个合并队列做前缀和，然后利用往后插的贡献来计算。
\(ht' + add * upd \to ht\)
\(s * upd + ht' * len\to hs\)
下文：
\(x \to adda, y \to addb\)
不带历史和的点积：
\((a + x)(b + y) \to ab + ay + bx + xy\)
\(sa * y' + sb * x' + x' * y' * len \to s\)
带上历史和？
\(x' * upd + ha' \to ha\)
\(y' * upd + hb' \to hb\)
\(x * y * upd + x * hb' + y * ha' + h' \to h\)
\(s * upd + x * hb' + y * ha' + h' * len \to ans\)
就是考虑维护对于 \(a/b\) 的标记历史和以及 \(a \times b\) 的标记历史和，其他和普通的历史和一样。
考虑产生的贡献，显然就是前面的在对后面的贡献、和后面组合、以及后面自己的值。
反正就是和普通历史和差不多就是了。
分别对应着三项贡献。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define lc x << 1
#define rc x << 1 | 1
/*王源他不发龙狙证明他没有素质*/
using namespace std;
typedef unsigned long long ull;
bool Mbe;
const int _ = 3e5 + 5;
bool Med;
int n, m;
struct Info {
ull sa, sb, s, ans, len;
};
Info operator + (Info x, Info y) {
Info z;
z.s = x.s + y.s,
z.sa = x.sa + y.sa,
z.sb = x.sb + y.sb,
z.ans = x.ans + y.ans;
z.len = x.len + y.len;
return z;
}
struct Tag {
ull adda, addb, ha, hb, h, upd;
} ;
struct node {
Info info;
Tag tag;
void apply (Tag k) {
info.ans += info.s * k.upd + info.sa * k.hb + info.sb * k.ha + k.h * info.len;
tag.h += tag.adda * tag.addb * k.upd + tag.adda * k.hb + tag.addb * k.ha + k.h;
tag.ha += tag.adda * k.upd + k.ha;
tag.hb += tag.addb * k.upd + k.hb;
info.s += k.adda * info.sb + k.addb * info.sa + k.adda * k.addb * info.len;
info.sa += k.adda * info.len;
info.sb += k.addb * info.len;
tag.adda += k.adda,
tag.addb += k.addb,
tag.upd += k.upd;
}
} tr[_ << 1];
void pushdown (int x) {
tr[lc].apply(tr[x].tag), tr[rc].apply(tr[x].tag);
tr[x].tag = {0, 0, 0, 0, 0, 0};
}
void build (int x, int l, int r) {
if (l == r) return tr[x].info.len = 1, void();
int mid = (l + r) >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
tr[x].info = tr[lc].info + tr[rc].info;
}
void modify (int x, int l, int r, int ql, int qr, Tag k) {
if (ql <= l && r <= qr) return tr[x].apply(k), void();
int mid = (l + r) >> 1; pushdown(x);
if (ql <= mid) modify(lc, l, mid, ql, qr, k);
if (qr > mid) modify(rc, mid + 1, r, ql, qr, k);
return tr[x].info = tr[lc].info + tr[rc].info, void();
}
ull query (int x, int l, int r, int ql, int qr) {
// cout << x << " " << l << " " << r << " " << tr[x].info.len << endl;
if (ql <= l && r <= qr) return tr[x].info.ans;
int mid = (l + r) >> 1;
ull ret = 0; pushdown(x);
if (ql <= mid) ret += query(lc, l, mid, ql, qr);
if (qr > mid) ret += query(rc, mid + 1, r, ql, qr);
return ret;
}
struct qry {int id, l; } ;
ull res[_], a[_], b[_];
int h1, h2, stka[_], stkb[_];
vector <qry> q[_];
int main () {
/*
freopen("match3.in", "r", stdin);
freopen("match.out", "w", stdout);
printf("%.3lfMB\n", fabs((&Mbe - &Med) / 1048576.0));
*/
ios_base :: sync_with_stdio(false);
cin.tie(0),
cout.tie(0);
int T;
cin >> T >> n;
rep(i, 1, n) cin >> a[i];
rep(i, 1, n) cin >> b[i];
cin >> m;
rep(i, 1, m) {
int l, r;
cin >> l >> r;
q[r].push_back({i, l});
}
build(1, 1, n);
rep(i, 1, n) {
while (h1 && a[stka[h1]] < a[i]) {
modify(1, 1, n, stka[h1 - 1] + 1, stka[h1], {-a[stka[h1]], 0, 0, 0, 0, 0});
h1 --;
}
modify(1, 1, n, stka[h1] + 1, i, {a[i], 0, 0, 0, 0, 0});
stka[++ h1] = i;
while (h2 && b[stkb[h2]] < b[i]) {
modify(1, 1, n, stkb[h2 - 1] + 1, stkb[h2], {0, -b[stkb[h2]], 0, 0, 0, 0});
h2 --;
}
modify(1, 1, n, stkb[h2] + 1, i, {0, b[i], 0, 0, 0, 0});
stkb[++ h2] = i;
tr[1].apply({0, 0, 0, 0, 0, 1});
for (auto & [id, l] : q[i]) res[id] = query(1, 1, n, l, i);
}
rep(i, 1, m) cout << res[i] << "\n";
return 0;
}