需要对某些区间递归处理的线段树的维护

标签：递归 线段 tr mid len ls 区间 mx

这篇总结来源于本蒟蒻打了两道题目发现了这种类型题，却不知道怎么给它起名字......

对一些已经看出来对区间进行操作和维护，但pushup操作不太容易想出来的题目来说，我们不妨尝试在两区间进行合并时，尝试对左或右区间进行递归，去除不正确的答案，维护区间的正解。

说起来的确很抽象（我甚至也不知道我在说什么），有一个运用这个方法的维护对象----单调栈：

以《楼房重建》这道题为例，这题是要维护从第一点开始的斜率单调递增的序列的点的个数（前缀单调递增序列）。

假设要对当前区间s进行pushup，左右子区间需要满足：右区间第一个对答案有贡献的点斜率大于左区间最大的斜率。

因此我们在线段树中维护两个值：最为答案的递增序列长度len，和该区间的最大值max。

首先l == r时，斜率不为0则return 1，否则return 0。

容易发现，s区间的左区间的所有点一定在答案内，因此s区间的len一定是：左区间的len + 右区间的贡献。

需要知道右区间的len不是它的贡献。有可能答案在左区间更新后，右区间的前几个点斜率会比左区间的新答案小。

因此对于右区间，我们把它劈成两个区间：r1和r2，设mx是s左区间的max。

r1和r2有两种情况：

    ①mx大于r1的最大值：此时r1所有的点都不对答案做出贡献，因此我们需要对r2操作。

也就是return pushup(rs, mid + 1, r, mi);

    ②mx小于等于r1的最大值：那么r2的对整个s右区间的贡献就能全部贡献到该区间中，只需要操作r1，

也就是pushup(ls, l, mid, mi) + tr[p].len - tr[ls].len;

这里是tr[p].len - tr[ls].len而不是tr[rs].len是因为，我们一直在递归pushup函数时，并未改变tr[p].len的值（除了递归入口的p），因此r2中还有许多点未必是能贡献到答案中的。这也是本题的，也是递归pushup线段树题目的难点。

 

类似的处理方式在李超线段树中也有过，即当大区间的答案不一定是更大区间的答案，也不一定是小区间的答案，我们需要一直递归下去或者找到绝对的递归出口。

这样的递归处理复杂度为O(logn)，它要在每个节点都要进行一次，总体的复杂度就是O(log^2 n)。

贴出丑陋的代码（楼房重建）：

#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cout<<endl<<#x<<": "<<x<<endl
#define endl "\n"
#define PII pair<int, int >
#define ls p << 1
#define rs (p << 1) + 1
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N = 1e5 + 10;

struct Segment_Tree {
    int len;
    double mx;
} tr[N << 2];

int n, m;
double k[N];

int pushup(int p, int l, int r, double mi) {
    if(l == r) return k[l] > mi;
    if(tr[p].mx <= mi) return 0;
    if(k[l] > mi) return tr[p].len;
    
    int mid = l + r >> 1;
    if(tr[ls].mx < mi) return pushup(rs, mid + 1, r, mi);
    else return pushup(ls, l, mid, mi) + tr[p].len - tr[ls].len;
}

void edit(int p, int l, int r, int x) {
    if(l == r && l == x) {
        tr[p].len = k[x] != 0;
        tr[p].mx = k[x];
        return ;
    }
    
    int mid = l + r >> 1;
    if(mid >= x) edit(ls, l, mid, x);
    else edit(rs, mid + 1, r, x);
    
    tr[p].mx = max(tr[ls].mx, tr[rs].mx);
    tr[p].len = tr[ls].len + pushup(rs, mid + 1, r, tr[ls].mx);
}

int main() {
    FAST;
    cin>>n>>m;
    
    int id;
    double y;
    while(m--) {
        cin>>id>>y;
        k[id] = (double) y / id;
        edit(1, 1, n, id);
        cout<<tr[1].len<<endl;
    }
    return 0;
}

 

标签：递归,线段,tr,mid,len,ls,区间,mx
From： https://www.cnblogs.com/killerboom/p/16736074.html