LG P5386 [Cnoi2019] 数字游戏 Solution

Description

给定一个排列 $p=(p_1,p_2,\cdots ,p_n)$，有 $q$ 次查询 $(l,r,L,R)$.
对每次查询，你需要求出满足以下条件的二元组 $(s,t)$ 的数量：

• $l\le s\le t\le r$
• 对任意 $s\le i\le t$ 都有 $L\le p_i\le R$.

Limitations

$1\le n,q\le 2\times 10^5$
$p_i$ 是 $1\sim n$ 的排列.
$1\le l\le r\le n$
$1\le L\le R\le n$
$7\text{s},125\text{MB}$

Solution

设 $b_i=[L\le a_i\le R]$，那么答案就是 $b_l\sim b_r$ 中连续全 $1$ 子段的个数.

考虑如何维护答案，对于一个区间，我们维护其前缀/后缀最长全 $1$ 子段的长度 $\text{pre},\text{suf}$，该区间的答案 $\text{sum}$，以及 $\text{full}$ 表示区间是否全为 $1$，合并操作很显然：

struct info {int pre, suf, full; i64 sum;inline info() : info(0, 0, 0, 0) {}inline info(int _pre, int _suf, int _full, i64 _sum): pre(_pre), suf(_suf), full(_full), sum(_sum) {}inline info operator+(const info& rhs) const {return info(pre + full * rhs.pre,rhs.suf + rhs.full * suf,full & rhs.full,sum + rhs.sum + 1LL * suf * rhs.pre);}
};

现在只需要对每个询问快速得到 $b_i$，注意到给定的是排列，每个数对应的位置唯一，设数字 $x$ 所在的下标为 $\mathrm{loc}(x)$.
考虑在值域 $[L,R]$ 上做莫队，每次 add/del 时直接单点修改 $b_{\mathrm{loc}(x)}$ 即可.

然后你发现 info 无交换律，不能用 $O(1)-O(\sqrt{n})$ 的分块维护，只能用单次 $O(\log n)$ 的线段树维护，但 $O(q\sqrt{n}\log n)$ 带上线段树大常数显然过不去.

考虑优化：

• fastio 什么的加上.
• 先给 $b_i$ 分块，再对每块开一个线段树，查询时整块直接查根，散块在线段树上递归，可以削掉查询的一半常数（因为 $\log \sqrt{n}=0.5\log n$）
• 注意到修改次数很多，所以可以不递归，直接自底向上迭代做，可以削掉递归的自带常数.

然后就可以过了.

Code

$5.63\text{KB},4.77\text{s},35.33\text{MB}\text{(C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}constexpr int S = 512;namespace Fastio {}
using Fastio::qin;
using Fastio::qout;constexpr int cap = 5e7 + 10;
int pool[cap], *ptr = pool;template<class T>
inline T* alloc(int n) {int siz = sizeof(T) / sizeof(int) * n;T* res = (T*)ptr; ptr += siz;return res;
}struct info {};struct segtree {struct node {int l, r;info dat;};node* tr;int* leaf;inline segtree() {}inline void init(int _n) {tr = alloc<node>(_n << 2);leaf = alloc<int>(_n);build(1, 0, _n - 1);}inline int ls(int u) { return u << 1; }inline int rs(int u) { return u << 1 | 1; }inline void build(int u, int l, int r) {tr[u].l = l, tr[u].r = r;if (l == r) return void(leaf[l] = u);const int mid = (l + r) >> 1;build(ls(u), l, mid);build(rs(u), mid + 1, r);}inline void update(int i, int v) {int u = leaf[i];tr[u].dat = {v, v, v, v};for (u >>= 1; u; u >>= 1) {tr[u].dat = tr[ls(u)].dat + tr[rs(u)].dat;}}inline info prod(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].dat;const int mid = (tr[u].l + tr[u].r) >> 1;if (r <= mid) return prod(ls(u), l, r);if (l > mid) return prod(rs(u), l, r);return prod(ls(u), l, r) + prod(rs(u), l, r);}inline info prod(int l, int r) { return prod(1, l, r); }inline info prod() { return tr[1].dat; }
};template<int B>
struct block {int n, blocks;segtree *blk;int *L, *R;inline block() {}inline block(int _n) : n(_n), blocks((_n + B - 1) / B) { blk = alloc<segtree>(blocks);L = alloc<int>(blocks);R = alloc<int>(blocks);for (int i = 0; i < blocks; i++) {L[i] = i * B, R[i] = min(L[i] + B, n) - 1;blk[i].init(R[i] - L[i] + 1);}}inline void update(int x, int v) { int b = x / B;blk[b].update(x - L[b], v); }inline info prod(int l, int r) {const int bl = l / B, br = r / B;if (bl == br) return blk[bl].prod(l - L[bl], r - L[bl]);info res = prod(l, R[bl]);for (int i = bl + 1; i < br; i++) res = res + blk[i].prod();return res + prod(L[br], r);}
};struct query {int l, r, x, y, id;inline query() {}inline query(int _l, int _r, int _x, int _y, int _id) : l(_l), r(_r), x(_x), y(_y), id(_id) {}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;qin >> n >> m;int *a = alloc<int>(n), *loc = alloc<int>(n);for (int i = 0; i < n; i++) {qin >> a[i], a[i]--;loc[a[i]] = i;}const int B = max(1, int(n / (sqrt(m) * 2 / 3)));block<S> blk(n);query *qry = alloc<query>(m);for (int i = 0, l, r, x, y; i < m; i++) {qin >> l >> r >> x >> y;l--, r--, x--, y--;qry[i] = query(l, r, x, y, i);}sort(qry, qry + m, [&](const query& a, const query& b) {return (a.x / B ^ b.x / B) ? (a.x / B < b.x / B) : ((a.x / B & 1) ? a.y > b.y : a.y < b.y);});i64 *ans = alloc<i64>(m);int l = 0, r = -1;for (int i = 0; i < m; i++) {auto [ql, qr, qx, qy, id] = qry[i];while (r < qy) blk.update(loc[++r], 1);while (l < qx) blk.update(loc[l++], 0);while (l > qx) blk.update(loc[--l], 1);while (r > qy) blk.update(loc[r--], 0);ans[id] = blk.prod(ql, qr).sum;}for (int i = 0; i < m; i++) qout << ans[i] << '\n';return 0;
}