P4198 楼房重建题解（线段树， 分治）

题目描述

题面

���要题意：

给你一个长度为 n n n 的序列 a i a_i ai​ ( n ≤ 1 0 5 n \leq 10^5 n≤105)，要求进行 m m m 次操作 ( m ≤ 1 0 5 m \leq 10^5 m≤105) 。操作分两种：

1.单点修改。

2.查询整个序列中有多少个位置 x x x 满足 a x a_x ax​ 大于其前缀。 即 ∀ j val，那么 r s n o d e rs_{node} rsnode​ 在 n o d e node node 对应区间的贡献就可以全部算进来。也就是说，如果 待求解区间的左半区间最大值大于 v a l val val，那么右半区间对 待求解区间的贡献 就等于其对 待求解区间的 s u m sum sum 的贡献。我们可以直接返回 c a l c ( l s n o d e , v a l ) + s u m n o d e − s u m l s n o d e calc(ls_{node}, val) + sum_{node} - sum_{ls_{node}} calc(lsnode​,val)+sumnode​−sumlsnode​​。

       如果 M a x n l s n o d e ≤ v a l Maxn_{ls_{node}} \leq val Maxnlsnode​​≤val，那可以发现左半区间是不会有贡献的，我们直接返回 c a l c ( r s n o d e , v a l ) calc(rs_{node}, val) calc(rsnode​,val) 就好。

       这样发现 c a l c calc calc 函数所求区间每次长度减半，最多执行 l o g 2 n log_2{n} log2​n 次。而线段树中每次修改最多 pushup l o g 2 n log_2n log2​n 次，因此复杂度是 O ( m l o g 2 2 n ) O(mlog_2^2n) O(mlog22​n)。

CODE：

// 问题模型化： 一个长度为n的序列，支持单点修改和在线查询整个序列有多少个位置上的值严格大于其前缀// sol: 线段树 + 分治 时间复杂度 O（nlog^2n）#includeusing namespace std;const int N = 1e5 + 10;typedef double db;struct SegmentTree {int l, r, sum; db Maxn; // sum 表示这个节点所在的区间（前缀的起始位置为区间左端点）有多少符合条件的点#define l(x) t[x].l#define r(x) t[x].r#define sum(x) t[x].sum#define Maxn(x) t[x].Maxn}t[N * 4];int n, m;db EPS = 1e-20;int calc(int p, db val) { // calc(p, val) 表示查询 p节点对应区间 大于val 并且大于其前缀的节点数if(l(p) == r(p)) {return (Maxn(p) > val);}if(Maxn(p  val) return (sum(p) - sum(p Maxn(p) = max(Maxn(p l(p) = l, r(p) = r;if(l == r) {sum(p) = 0;Maxn(p) = 0;return ;}int mid = (l + r  1);build(p if(l(p) == r(p)) {Maxn(p) = c;if(Maxn(p) - 0.0