带区间限制的线段树二分

· · 算法·理论

::::info[前言] 全站推荐理由:带区间限制的线段树二分,很有实用性的技巧,值得学习,但网络上相关资源匮乏,而本文实现方法简洁易懂。最重要的是我想水社贡。 ::::

Part 1 线段树区间离线

当处理区间询问时,我们有时并不方便去每次合并两个儿子的答案,所以需要将线段树上区间离线下来再进行合并或其他操作。

例题:P16702 [MCO 2026] 雨水收集 - 洛谷

题解:题解:P16702 [MCO 2026] 雨水收集 - 洛谷专栏

在单侧递归线段树中,由于在合并时有向下递归的操作,不太好直接在查询递归时处理答案的合并,所以考虑先把(查询区间中的(线段树上的节点))离线下来,再从左到右把这些区间扫一遍,进行答案的合并。

考虑这张经典的线段树。如果我们要查询蓝色区间,就会把 2, 6, 14 号节点离线下来,然后维护一个答案,从左到右把答案和当前考虑到的节点像左右儿子那样合并。

大概代码如下,具体可看题解。

::::success[Code]


struct Node {
    int u, l, r;
};

vector<Node> s;

void Get(int u, int l, int r, int ql, int qr) { // 离线区间
    if (qr < l || r < ql) return ;
    if (ql <= l && r <= qr) {
        s.push_back({u, l, r});
        return ;
    }
    Down(u, l, r);
    int mid = l + r >> 1;
    Get(u << 1, l, mid, ql, qr);
    Get(u << 1 | 1, mid + 1, r, ql, qr);
    return ;
}

Node Query(int l, int r) {
    s.clear();
    Get(1, 1, n, l, r); 
    Node x = E; // 答案
    for (auto _ : s) {
        x.sum += t[_.u].sum;
        x.a = x.a + Calc1(_.u, _.l, _.r, x.mx);
        x.mx = max(x.mx, t[_.u].mx);
    }
    reverse(s.begin(), s.end());
    x.mx = -INF;
    for (auto _ : s) {
        x.b = Calc2(_.u, _.l, _.r, x.mx) + x.b;
        x.mx = max(x.mx, t[_.u].mx);
    }
    return x;
}

::::

Part 2 带区间限制的线段树二分

考虑以下问题。

给定一个长度为 n 的序列 \{a_i\},和两个整数 P, Q。要求满足以下条件的最长的连续区间 [l, r],若存在相同长度的区间,则输出 l 最小的一个。

  1. 令 u = \sum\limits_{l < i \le r} [a_{i - 1} < a_{i}],v = \sum\limits_{l < i \le r} [a_{i - 1} > a_{i}],则 |u - v| \le Q。

考虑扫描线枚举右端点。

当右端点确定时。容易发现满足第一条的左端点是一定一个后缀。而第二条可以考虑对 [a_{i - 1} < a_i] - [a_{i - 1} > a_i] 前缀和,记为 s_i。则合法的 s_l 是一个区间。于是,我们要查询所有 s_i 属于这个区间的 i 中,第一个大于第一条的后缀限制的位置。

考虑使用主席树,对每一个 k 建一个线段树,给 s_i \le k 的 i 打标记(加一),维护区间和。这样就可以用主席树上二分来求解上文的位置。

可是,这里二分的范围是一段区间,需要特殊地处理。

我们发现一般的线段树上二分的时候需要利用二分的范围恰好是线段树所覆盖的范围这一性质。而当我们要在限定的区间上二分时,则没有这一性质。于是,考虑把区间中的所有线段树上节点离线下来,先在这些从左到右覆盖位置不成不漏的节点上找到第一个存在合法位置的节点,然后对其线段树上二分。

比较好写。具体代码如下。容易知道我们最终得到的是 O(n \log n) 的时间复杂度。

::::success[Code]

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e6 + 5, L = 20;

struct Seg {
    int u, l, r;
};

struct Node {
    int sum, l, r;
};

int n, m, P, Q, ans, Lt, tot;
int a[N], d[N], s[N], f[N][L], g[N][L], lg[N], root[N];
Node t[N << 2];
vector<int> p[N]; 
vector<Seg> seg;

int Qmx(int l, int r) {
    int k = lg[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int Qmn(int l, int r) {
    int k = lg[r - l + 1];
    return min(g[l][k], g[r - (1 << k) + 1][k]);
}

int Clone(int u) {
    t[++tot] = t[u];
    return tot;
}

int Update(int u, int l, int r, int x, int v) {
    if (x < l || r < x) return u;
    u = Clone(u);
    if (l == r) {
        t[u].sum += v;
        return u;
    }
    int mid = l + r >> 1;
    t[u].l = Update(t[u].l, l, mid, x, v);
    t[u].r = Update(t[u].r, mid + 1, r, x, v);
    t[u].sum = t[t[u].l].sum + t[t[u].r].sum;
    return u;
}

void Get(int u, int l, int r, int ql, int qr) { // 离线区间
    if (qr < l || r < ql) return ;
    if (ql <= l && r <= qr) {
        seg.push_back({u, l, r});
        return ;
    }
    int mid = l + r >> 1;
    Get(t[u].l, l, mid, ql, qr);
    Get(t[u].r, mid + 1, r, ql, qr);
    return ;
}

int Query(int x, int y, int l, int r) { // 线段树上二分
    if (l == r) return l;
    int mid = l + r >> 1;
    if (t[t[y].l].sum - t[t[x].l].sum > 0) {
        return Query(t[x].l, t[y].l, l, mid);
    } else {
        return Query(t[x].r, t[y].r, mid + 1, r);
    }
}

int QQ(int ul, int ur, int p) {//寻找 [l, n] 中第一个 s_i 在合法区间内的位置
    vector<Seg> x, y;
    seg.clear();
    Get(ul, 1, n, p, n);
    x = seg;
    seg.clear();
    Get(ur, 1, n, p, n);
    y = seg;
    for (int i = 0; i < x.size(); i++) {
        int u = x[i].u, v = y[i].u;
        if (t[u].sum < t[v].sum) {
            return Query(u, v, x[i].l, x[i].r);
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> P >> Q;
    m = n + 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
        if (d[i] > 0) d[i] = 1;
        if (d[i] < 0) d[i] = -1;
        s[i] = s[i - 1] + d[i];
        p[m + s[i]].push_back(i);
    }
    for (int i = -n; i <= n; i++) {
        root[m + i] = root[m + i - 1];
        for (int x : p[m + i]) {
            root[m + i] = Update(root[m + i], 1, n, x, 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        lg[i] = i == 1 ? 0 : lg[i >> 1] + 1;
        f[i][0] = g[i][0] = a[i];
    }
    for (int i = 1; i < L; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            f[j][i] = max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
            g[j][i] = min(g[j][i - 1], g[j + (1 << i - 1)][i - 1]);
        }
    }
    for (int i = 1, j = 1; i <= n; i++) {
        for (; j < n && Qmx(j, i) - Qmn(j, i) > P; j++) ; // 合法后缀
        int l = max(s[i] - Q, -n) - 1, r = min(s[i] + Q, n); // s_l 的合法区间
        int lt = QQ(root[m + l], root[m + r], j);
        int len = i - lt + 1;if (ans < len) {
            ans = len;
            Lt = i - len + 1;
        }
    }
    cout << ans << ' ' << Lt; 
    return 0;
}

::::

差不多了。虽然这篇比较短,但还是希望大家看了能点个赞!