（紫，莫队，线段树，微扰法）P6349 [PA 2011] Kangaroos 题解

莫队思想

考虑莫队，由于询问的是区间，故按照值域跑。我们考虑计算区间加上或减去一个端点时会产生的变化。如果我们向左侧扩展一个点，新产生交集的区间则为所有以该点为右端点的区间，向右侧扩展同理。删除端点则是删去这样的区间，也同理。

线段树求最长段

我们要求求出最长的连续有交集的区间。于是不难想到建一棵下标线段树，每个叶子结点的为，表示该元素当前有没有被选到。接下来向上 pushup。

pushup 思想为通过当前合并的两个区间的前缀和后缀的长度计算。核心代码如下：

void pushup(int p) {
    tr[p].pre = tr[p << 1].pre + tr[p << 1 | 1].pre * (tr[p << 1].pre == tr[p << 1].len);
    tr[p].suf = tr[p << 1 | 1].suf + tr[p << 1].suf * (tr[p << 1 | 1].suf == tr[p << 1 | 1].len);
    tr[p].res = max({ tr[p << 1].res, tr[p << 1 | 1].res, tr[p << 1].suf + tr[p << 1 | 1].pre });
}

最终，tr[1].res 即为当前最长段。

朴素的离散化

我们肯定要将所有离散化。对于询问内容我们如果也加入离散化，由于在数量级上有所差异，后期计算的常数会非常大。于是，我们不妨将向里缩到最近的和的值，发现这样的转化是不影响答案的。为所有离散化后的全集，代码如下：

que[i].l = lower_bound(a + 1, a + m + 1, que[i].l) - a;
que[i].r = lower_bound(a + 1, a + m + 1, que[i].r) - a;

退化的风险

这个做法看似很完美，但是有一个致命的错误。我们莫队在移动端点时，如果改变的那个端点对应着极多的区间，那我们就需要将这些区间全部加入线段树。如果数据设计为反复插入和删除这个点，复杂度直接爆炸，退化为。

提交发现会得到 TLE 分。

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fstrict-aliasing")

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2e5 + 5;

int n, m, B, tot, q, ans[N];
int L = 1, R = 0;
int l[N], r[N], a[N], ps[N];

vector<int> posL[N], posR[N];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct query {
    int l, r;
    int id;
    bool operator < (const query& o) const {
        int id1 = l / B, id2 = o.l / B;
        if (id1 != id2) { return id1 < id2; }
        if (id1 % 2) { return r < o.r; }
        return r > o.r;
    }
} que[N];

struct seg {
    
    struct node {
        int pre, suf, res, len;
    } tr[N << 2];

    void pushup(int p) {
        int ls = (p << 1), rs = (p << 1 | 1);
        tr[p].pre = tr[ls].pre + (tr[ls].pre == tr[ls].len ? tr[rs].pre : 0);
        tr[p].suf = tr[rs].suf + (tr[rs].suf == tr[rs].len ? tr[ls].suf : 0);
        tr[p].res = max({ tr[ls].res, tr[rs].res, tr[ls].suf + tr[rs].pre });
    }

    void build(int l = 1, int r = n, int p = 1) {
        tr[p].len = r - l + 1;
        if (l == r) {
            ps[l] = p;
            tr[p].res = tr[p].pre = tr[p].suf = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, p << 1);
        build(mid + 1, r, p << 1 | 1);
        pushup(p);
    }

    void update(int x, int k) {
        int p = ps[x];
        tr[p].res = tr[p].pre = tr[p].suf = k;
        while (p >>= 1) { pushup(p); }
    }

    int query() { return tr[1].res; }
    
} T;

void insL(int x) { for (int i : posR[x]) { T.update(i, 1); } }
void insR(int x) { for (int i : posL[x]) { T.update(i, 1); } }
void delL(int x) { for (int i : posR[x]) { T.update(i, 0); } }
void delR(int x) { for (int i : posL[x]) { T.update(i, 0); } }

void solve() {
    n = read(), q = read();
    B = sqrt(n);
    for (int i = 1; i <= n; i++) {
        l[i] = read(), r[i] = read();
        a[++tot] = l[i];
        a[++tot] = r[i];
    }
    for (int i = 1; i <= q; i++) {
        que[i].l = read(), que[i].r = read();
        que[i].id = i;
    }
    sort(a + 1, a + tot + 1);
    m = unique(a + 1, a + tot + 1) - a - 1;
    for (int i = 1; i <= n; i++) {
        l[i] = lower_bound(a + 1, a + m + 1, l[i]) - a;
        r[i] = lower_bound(a + 1, a + m + 1, r[i]) - a;
        posL[l[i]].push_back(i);
        posR[r[i]].push_back(i);
    }
    for (int i = 1; i <= q; i++) {
        que[i].l = lower_bound(a + 1, a + m + 1, que[i].l) - a;
        que[i].r = upper_bound(a + 1, a + m + 1, que[i].r) - a - 1;
    }
    T.build();
    sort(que + 1, que + q + 1);
    for (int i = 1; i <= q; i++) {
        while (que[i].l < L) { insL(--L); }
        while (que[i].r > R) { insR(++R); }
        while (que[i].l > L) { delL(L++); }
        while (que[i].r < R) { delR(R--); }
        ans[que[i].id] = T.query();
    }
    for (int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
}

int main() {
    solve();
    return 0;
}

微扰法

我们有一种新颖的离散化技巧，叫做微扰法，为将所有左端点在离散化前减去之间的随机实数，右端点加上，此后再离散化。这样就可以做到所有端点都是互不相同的，就可以防止一次性将一堆点加入线段树，从而规避掉算法退化的错误。

时间复杂度：。

代码实现（可 AC）：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2e5 + 5;

int n, m, B, tot, q, ans[N];
int L = 1, R = 0;
double l[N], r[N], a[N];

double rand01() {
    int r = rand();
    return (double)r / (double)INT_MAX / 2.0001;
}

vector<int> posL[N], posR[N];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct query {
    int l, r;
    int id;
    bool operator < (const query& o) const {
        int id1 = l / B, id2 = o.l / B;
        if (id1 != id2) { return id1 < id2; }
        if (id1 % 2) { return r < o.r; }
        return r > o.r;
    }
} que[N];

struct seg {
    
    struct node {
        int l, r, pre, suf, res, len;
    } tr[N << 2];

    void pushup(int p) {
        tr[p].pre = tr[p << 1].pre + tr[p << 1 | 1].pre * (tr[p << 1].pre == tr[p << 1].len);
        tr[p].suf = tr[p << 1 | 1].suf + tr[p << 1].suf * (tr[p << 1 | 1].suf == tr[p << 1 | 1].len);
        tr[p].res = max({ tr[p << 1].res, tr[p << 1 | 1].res, tr[p << 1].suf + tr[p << 1 | 1].pre });
    }

    void build(int l = 1, int r = n, int p = 1) {
        tr[p].l = l, tr[p].r = r;
        tr[p].len = tr[p].r - tr[p].l + 1;
        if (tr[p].l == tr[p].r) {
            tr[p].res = tr[p].pre = tr[p].suf = 0;
            return;
        }
        int mid = (tr[p].l + tr[p].r) >> 1;
        build(l, mid, p << 1);
        build(mid + 1, r, p << 1 | 1);
        pushup(p);
    }

    void update(int x, int k, int p = 1) {
        if (tr[p].l == tr[p].r) {
            tr[p].res = tr[p].pre = tr[p].suf = k;
            return;
        }
        int mid = (tr[p].l + tr[p].r) >> 1;
        if (x <= mid) {
            update(x, k, p << 1);
        } else {
            update(x, k, p << 1 | 1);
        }
        pushup(p);
    }

    int query() { return tr[1].res; }
    
} T;

void insL(int x) { for (int i : posR[x]) { T.update(i, 1); } }
void insR(int x) { for (int i : posL[x]) { T.update(i, 1); } }
void delL(int x) { for (int i : posR[x]) { T.update(i, 0); } }
void delR(int x) { for (int i : posL[x]) { T.update(i, 0); } }

void solve() {
    srand(time(0));
    n = read(), q = read();
    B = sqrt(n);
    for (int i = 1; i <= n; i++) {
        l[i] = read(), r[i] = read();
        l[i] -= rand01(), r[i] += rand01();
        a[++tot] = l[i];
        a[++tot] = r[i];
    }
    for (int i = 1; i <= q; i++) {
        que[i].l = read(), que[i].r = read();
        que[i].id = i;
    }
    sort(a + 1, a + tot + 1);
    m = unique(a + 1, a + tot + 1) - a - 1;
    for (int i = 1; i <= n; i++) {
        l[i] = lower_bound(a + 1, a + m + 1, l[i]) - a;
        r[i] = lower_bound(a + 1, a + m + 1, r[i]) - a;
        posL[(int)l[i]].push_back(i);
        posR[(int)r[i]].push_back(i);
    }
    for (int i = 1; i <= q; i++) {
        que[i].l = lower_bound(a + 1, a + m + 1, que[i].l) - a;
        que[i].r = upper_bound(a + 1, a + m + 1, que[i].r) - a - 1;
    }
    T.build();
    sort(que + 1, que + q + 1);
    for (int i = 1; i <= q; i++) {
        while (que[i].l < L) { insL(--L); }
        while (que[i].r > R) { insR(++R); }
        while (que[i].l > L) { delL(L++); }
        while (que[i].r < R) { delR(R--); }
        ans[que[i].id] = T.query();
    }
    for (int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
}

int main() {
    solve();
    return 0;
}

回滚莫队优化（口胡）

我们考虑优化掉。注意到将一个点删掉维护是困难的，而加入点事容易的。加入点时，可能会合并两边的区间，此时用一个链表维护就可以了。

于是采用回滚莫队，只加点，不删点。但是我不想写，所以口胡一下。