当前位置: 首页 > news >正文

题解:Luogu P2075 区间 LIS

题意

给定长度为 \(n\) 的排列 \(p\)\(q\) 次询问 \(l,r\),求 \(p[l,r]\) 的 LIS 长度。\(1\leq n,q\leq 10^5\)

题解

挺牛的题。

考虑如何刻画 LIS。感觉上 DP 没有什么前途,考虑另一种经典的 \(\mathcal{O}(n\log{n})\) 求 LIS 的方法:维护 \(f_i\) 表示长度为 \(i\) 的 LIS 的最小结尾元素,初始时 \(\forall 1\leq i\leq n,f_i\leftarrow +\infty\),当添加元素 \(x\) 时,对于每个 \(f_i<x\)\(i\),令 \(f_{i+1}\leftarrow \min(f_{i+1},x)\)。注意到 \(f\) 单调不减,所以上述过程实际上等价于找到最小的 \(i\) 使得 \(f_i\geq x\),令 \(f_i\leftarrow x\)

简化这个过程:我们维护 \(S\) 表示 \(f\) 中所有非 \(+\infty\)\(f_i\),初始时 \(S\leftarrow\varnothing\),每次插入 \(x\) 时,若 \(\max\limits_{y\in S}y<x\),则向 \(S\) 中插入 \(x\),否则将 \(S\) 中最小的 \(\geq x\) 的元素改为 \(x\)。最终答案就是 \(|S|\)

回到原题,考虑对右端点 \(r\) 做扫描线,对每个左端点 \(l\) 维护 \(S_{l,r}\) 表示对 \(p[l,r]\) 中元素依次执行上述操作得到的集合。我们当然不可能直接存下来所有的 \(S\),考虑找一些性质。通过手玩样例,我们会发现 \(S_{l,r}\subseteq S_{l-1,r}\)\(|S_{l-1,r}|-|S_{l,r}|\leq 1\)

证明:令 \(S_1\leftarrow\varnothing,S_2\leftarrow \{p_{l-1}\}\),我们遍历 \(p[l,r]\) 中的每个元素,同时对 \(S_1,S_2\) 执行操作。不难看出,每次插入 \(x\) 时,若 \(p_{l-1}\) 没有成为最小的 \(\geq x\) 的元素,则始终有 \(S_2=S_1\cup\{p_{l-1}\}\);否则,\(S_2\)\(p_{l-1}\) 会被修改为 \(x\),且对于 \(S_1\)

  • \(S_1\) 中所有元素 \(<x\),则 \(x\) 插入到 \(S_1\) 中后,我们有 \(S_2=S_1\)
  • \(S_1\) 中存在元素 \(\geq x\),记最小的元素为 \(y\),则 \(S_1\)\(y\) 会被修改为 \(x\),此时我们有 \(S_2=S_1\cup\{y\}\),也就是说 \(y\) 会代替 \(x\) 成为新的元素来保持 \(S_1,S_2\) 间的差异。

可以看出,这样子不断将操作执行下去,要么 \(S_2\) 会在某个时刻变得与 \(S_1\) 相等,要么 \(S_2\) 始终保持 \(S_1\subseteq S_2\land |S_2|-|S_1|\leq 1\)\(\Box\)

根据这个性质,一个数 \(x\) 必然会在一段前缀的 \(l\) 对应的 \(S_{l,r}\) 中出现,由此,我们可以从值域上考虑,对于每个数 \(x\) 维护 \(a_x\) 表示最大的 \(l\) 使得 \(x\in S_{l,r}\)。那么询问 \([l,r]\) 的答案时,只需查询有多少 \(x\) 满足 \(a_x\geq l\) 即可。

考虑每次 \(r\leftarrow r+1\)\(a\) 的变化。令 \(v=p_r\),则显然 \(a_v\leftarrow r\)。进一步考察 \(v+1\),若 \(a_{v+1}>0\),也就是 \(v+1\) 在某些 \(S_{l,r}\) 中出现,则 \(a_{v+1}\leftarrow 0\)。对于 \(v+2\),考虑包含它的某个 \(S_{l,r}\),只有在 \(v+1\in S_{l,r}\)\(v+2\) 才不会被修改,因此若最开始时 \(a_{v+1}>0\),则 \(a_{v+2}\leftarrow a_{v+1}\),否则 \(a_{v+2}\leftarrow 0\)

以此类推,可以发现对 \(a\) 的影响形如:有一个值 \(x\),初始时 \(x\)\(0\),依次遍历 \(i=v+1,v+2,\cdots,n\)

  • \(a_i>x\),交换 \(a_i\)\(x\) 的值。

这其实就是回转寿司中的操作。

考虑分块。不妨先想整块怎么做。此时我们不妨只关注块中元素构成的可重集 \(S\) 的变化。设 \(S\) 中元素的最大值为 \(mx\),考虑不同的 \(x\) 带来的影响:

  • \(x\geq mx\):操作对该块没有影响。
  • \(x<mx\):此时我们会从 \(S\) 中删除 \(mx\),再插入 \(x\)。而 \(x\) 的值会对应变成 \(mx\)

于是我们只需在每个块上用一个大根堆维护 \(S\) 即可。

再来考虑散块怎么做。由于处理整块时我们只关心元素构成的可重集,所以每个位置对应的数我们并不清楚。考虑如何由整块上的所有操作构成的可重集 \(P=\{x_1,x_2,\cdots,x_m\}\),还原整块中每个位置对应的数。

不妨先考察整块中的第一个元素 \(a_p\) 如何变化。考虑 \(mn=\min\limits_{x\in P}x\),不难发现若 \(mn\geq a_p\) 则无事发生,否则 \(a_p\) 会变成 \(mn\),并且此时,我们可以等效地在 \(P\) 中用 \(a_p\) 代替 \(mn\)。对于 \(a_{p+1}\),同样考察 \(P\) 中最小值即可,以此类推。我们发现,我们完全可以用和刚才类似的方法维护这个过程,更具体地,我们用小根堆维护 \(P\),然后遍历块中元素对应更新即可。

我们用权值 BIT 维护 \(a\) 中的值,那么每次操作先在 \(a_v=r\) 上单点加,然后对于接下来的回转寿司操作,先在 \(0\) 上单点加 \(1\),然后在最后得到的 \(x\) 上单点减 \(1\) 即可。

设块长为 \(B\),则时间复杂度为 \(\mathcal{O}((B+\dfrac{n}{B})\log{n}+q\log{n})\),取 \(B=\sqrt{n}\) 即可 \(\mathcal{O}(\sqrt{n}\log{n}+q\log{n})\) 地解决本题。当然也可以用值域分块把 \(q\) 后面的 \(\log\) 搞掉,没啥必要就是了。

代码

int n, q, B, a[N], p[N], ans[N];
int bl[N], lb[BC], rb[BC];
priority_queue<int> P[BC];
priority_queue<int, vector<int>, greater<>> Q[BC];
struct Query { int id, l, r; } qr[N];struct BIT {int c[N];inline int query(int x) {int res = 0;for (++x; x <= n + 1; x += lowbit(x)) res += c[x];return res;}inline void add(int x, int v) { for (++x; x; x -= lowbit(x)) c[x] += v; }
} ft;inline void rebuild(int id) {auto &pq = Q[id];if (pq.empty()) return;int l = lb[id], r = rb[id];for (int i = l; i <= r; ++i)if (a[i] > pq.top()) pq.push(a[i]), a[i] = pq.top(), pq.pop();priority_queue<int, vector<int>, greater<>>().swap(pq);
}
inline int query(int l, int r, int x) {int b1 = bl[l], b2 = bl[r];if (b1 == b2) {rebuild(b1);for (int i = l; i <= r; ++i) if (a[i] > x) swap(a[i], x);return priority_queue<int>(a + lb[b1], a + rb[b1] + 1).swap(P[b1]), x;}rebuild(b1), rebuild(b2);for (int i = l; i <= rb[b1]; ++i) if (a[i] > x) swap(a[i], x);priority_queue<int>(a + lb[b1], a + rb[b1] + 1).swap(P[b1]);for (int i = b1 + 1, tp; i < b2; ++i) {if (x >= P[i].top()) continue;Q[i].push(x);P[i].push(x), x = P[i].top(), P[i].pop();}for (int i = lb[b2]; i <= r; ++i) if (a[i] > x) swap(a[i], x);return priority_queue<int>(a + lb[b2], a + rb[b2] + 1).swap(P[b2]), x;
}int main() {ios::sync_with_stdio(0), cin.tie(0);n = rd(), q = rd(), B = BL - 5;for (int i = 1; i <= n; ++i) p[i] = rd();for (int i = 1, l, r; i <= q; ++i) l = rd(), r = rd(), qr[i] = {i, l, r};for (int i = 1, j = 1; j <= n; ++i) {lb[i] = j, rb[i] = min(j + B - 1, n);priority_queue<int>(a + lb[i], a + rb[i] + 1).swap(P[i]);for (int u = rb[i]; j <= u; ++j) bl[j] = i;}sort(qr + 1, qr + q + 1, [](const Query &x, const Query &y) { return x.r < y.r; });ft.add(0, n);for (int i = 1, j = 1; i <= n; ++i) {int val = p[i];if (val < n) {int x = query(val + 1, n, 0);ft.add(x, -1), ft.add(0, 1);}int b = bl[val];rebuild(b);ft.add(a[val], -1), ft.add(a[val] = i, 1);priority_queue<int>(a + lb[b], a + rb[b] + 1).swap(P[b]);while (j <= q && qr[j].r == i) ans[qr[j].id] = ft.query(qr[j].l), ++j;}for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=35338

相关文章:

  • 英语_阅读_2050 Space tourism_待读
  • goframe框架命令行工具gf在zsh下不能用
  • 题解:Luogu P4143 采集矿石
  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统
  • CSP-S 35
  • CSP-S 29
  • 2025网络安全振兴杯wp
  • 10.20每日总结
  • CSP-S 31
  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)
  • 服务器CPU市场概况2025
  • CSP-S 24
  • 读书笔记:深入理解java虚拟机
  • CSP-S 19
  • CSP-S 20