[PA 2011] Kangaroos（复杂回滚莫队）题解

Blue_Fish_Junly · 2026-05-09 14:51:09 · 题解

给 n 个闭区间 [l_i,r_i]，接下来 m 次询问，每次给定 [A,B]，你需要找到满足下述条件的 x,y：
\forall p \in [x,y], [l_p,r_p] \cap [A,B] \neq \varnothing
最大化并输出合法的 |y-x+1|。

考虑对于每个询问，可以怎样转化题面。

不妨对于每个询问 [A_i,B_i] 维护长度为 n 的布尔值序列 s，如果 [A_i,B_i] \cap [l_j,r_j] \neq \varnothing 就让 s_j 为 1，否则令其为 0。

题意立即转化为两个部分：

合理提出若干次修改要求和询问要求。
动态地变换布尔序列，并在询问时返回最大长度的连续 1 段。

看第一个部分。

我们来尝试找到两个区间交不为空的充要条件，容易发现：

[A,B] \cap [l,r] \neq \varnothing ~~~ \Leftrightarrow ~~~ r \ge A \textrm{ and } l \le B

观察这个式子，注意到两个区间是否相交仅与其相对大小有关，这启示我们对所有的线段端点进行离散化操作。

这样一来，下标区间上界最坏就是 V=2n+2m，该值可以达到 V=5 \times 10^5。

你会发现现在如果在已有线段中加入一个新的值，这将是非常好维护的，很类似于莫队的形式。

考虑对询问中左端点分块并以左端点对应块编号为第一关键字、右端点为第二关键字排序，于是我们得到了一个 \mathcal{O}(V \sqrt{V}) 的询问转移。

发现此时问题瓶颈在于如何快速找出与询问相交的线段并将其加入布尔序列的考量。

一种挺显然的思路是，在序列扩张时，指针若遇线段端点，那么这两条线段就一定相交。

然而，该思路无法解决的是，一条原线段完完全全地包住了这个询问。这样一来，指针始终无法动到外侧线段的端点。

我们注意到如果外侧线段包住内侧线段，则属于内侧线段的每一个点都属于外侧线段。

根据不删除莫队的传统，我们来分两类讨论。第一类就是跨块的询问，第二种就是单块的询问。

我们先看跨块的，容易发现块的右端点是其必经之点，故若一个原线段包裹住该询问，则其必包住块的右端点。

所以对于跨块的询问，交不为空的充分必要条件就是满足下面两个条件之一：

左端点所在块的右端点属于原线段。
指针扩张时碰到了原线段的端点。

再来看块内的。同样的道理，为了包住它，我们需要满足下面这三个条件之一：

大线段的左端点在所在块的左端点之左，右端点在所在块的右端点之右。
大线段的端点在块内，且与询问相交。
指针扩张时碰到了原线段的端点。

容易注意到，时间复杂度的瓶颈在于 2。为了处理这种情况，我们要保证在一个块内的端点数量在根号的量级。

因为可能会有很多个点重合，考虑魔改离散化，定义 \textrm{new}_x 为 x 离散化之后的值，我们要保证：

若 A_i=B_j，则令 \textrm{new}_{A_i} < \textrm{new}_{B_j}；
若 A_i=l_k（r_k 同理），则令 \textrm{new}_{A_i} < \textrm{new}_{l_k}；
若 B_j=l_k（r_k 同理），则令 \textrm{new}_{l_k} < \textrm{new}_{B_j}。

这样就形成了一个两两不重的离散化，之后可以直接按照值域分块，复杂度控制在了 \mathcal{O}(V \sqrt{m})。

然后这个时候你发现如果使用不删除莫队，第二部分就是要支持插入 1，并动态维护最长的线段。直接开链表，对于每个点维护其延伸出的最左和最右的节点即可，时间复杂度 \mathcal{O}(1)。

此题可解。

:::success[参考代码]

#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
#define N 500002
#define length 780
using std::vector;
using std::sort;

char trail_in[1<<18],*p1=trail_in,*p2=trail_in,ch;
char trail_out[1<<21],*p3=trail_out;
constexpr char *p4=trail_out+(1<<21);
bool cat;
inline char gc() {
    if(p1==p2) {
        p2=(p1=trail_in)+fread(trail_in,1,1<<18,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
inline void pc(char C) {
    if(p3==p4) {
        fwrite(trail_out,1,1<<21,stdout);
        p3=trail_out;
    }
    *p3++=C;
}
template<typename _Tp>
inline void read(_Tp &fish) {
    cat=true, fish=0, ch=' ';
    do cat&=(ch!='-');
    while((ch=gc())<48);
    do fish=(fish<<3)+(fish<<1)+(ch^48);
    while((ch=gc())>47);
    fish=cat?fish:-fish;
}
template<typename _Tp>
inline void write(_Tp x) {
    if(x<0) pc('-'), x=-x;
    if(x>9) write(x/10);
    pc(x%10+48);
}
struct Flusher {
    ~Flusher() {
        if(p3!=trail_out) fwrite(trail_out,1,p3-trail_out,stdout);
    }
} Output_Tool;
struct Numbers {
    short opt; // opt: 1 表示 A，2 表示 l，3 表示 r，4 表示 B
    int plc,val;
    inline bool operator < (const Numbers &p) const {
        if(val!=p.val) return val<p.val;
        return opt<p.opt;
    }
};
vector<Numbers> vec;
struct Queries {
    int l,r,id;
    inline bool operator < (const Queries &p) const {
        return r<p.r;
    }
};
vector<Queries> flc[1002];
struct Memories {
    bool dir;
    int plc,val;
};
vector<Memories> jun;
int n,m,toola,toolb,L[N],R[N],A[N],B[N],ans[N],own[N],maxn,maxn_memo;
int Llink[N],Rlink[N];
inline void ins1(int x) { // 对于一个块维护的序列，永久地加入 x 这个元素
    if(Llink[x] or Rlink[x]) return;
    if(Llink[x-1] and Rlink[x+1]) {
        int le=Llink[x-1],re=Rlink[x+1];
        Rlink[le]=Rlink[x]=re;
        Llink[re]=Llink[x]=le;
        if (maxn<re-le+1) maxn=re-le+1;
    } else if(Llink[x-1]) {
        Llink[x]=Llink[x-1];
        Rlink[Llink[x]]=x;
        Rlink[x]=x;
        if(maxn<x-Llink[x]+1) maxn=x-Llink[x]+1;
    } else if(Rlink[x+1]) {
        Rlink[x]=Rlink[x+1];
        Llink[Rlink[x]]=x;
        Llink[x]=x;
        if(maxn<Rlink[x]-x+1) maxn=Rlink[x]-x+1;
    } else {
        Llink[x]=Rlink[x]=x;
        if(maxn<1) maxn=1;
    }
}
inline void ins2(int x) { // 对于一个块维护的序列，暂时地加入 x 这个元素
    if(Llink[x] or Rlink[x]) return;
    if(Llink[x-1] and Rlink[x+1]) {
        int le=Llink[x-1],re=Rlink[x+1];
        jun.push_back({1,le,Rlink[le]});
        jun.push_back({0,re,Llink[re]});
        jun.push_back({0,x,Llink[x]});
        jun.push_back({1,x,Rlink[x]});
        Rlink[le]=Rlink[x]=re;
        Llink[re]=Llink[x]=le;
        if(maxn<re-le+1) maxn=re-le+1;
    } else if(Llink[x-1]) {
        jun.push_back({0,x,Llink[x]});
        jun.push_back({1,x,Rlink[x]});
        jun.push_back({1,Llink[x-1],Rlink[Llink[x-1]]});
        Llink[x]=Llink[x-1];
        Rlink[Llink[x]]=x;
        Rlink[x]=x;
        if(maxn<x-Llink[x]+1) maxn=x-Llink[x]+1;
    } else if(Rlink[x+1]) {
        jun.push_back({0,x,Llink[x]});
        jun.push_back({1,x,Rlink[x]});
        jun.push_back({0,Rlink[x+1],Llink[Rlink[x+1]]});
        Rlink[x]=Rlink[x+1];
        Llink[Rlink[x]]=x;
        Llink[x]=x;
        if(maxn<Rlink[x]-x+1) maxn=Rlink[x]-x+1;
    } else {
        jun.push_back({0,x,Llink[x]});
        jun.push_back({1,x,Rlink[x]});
        Llink[x]=Rlink[x]=x;
        if(maxn<1) maxn=1;
    }
}
inline void shower1() { // 清掉一个块的贡献
    for(int i=0; i<=n+1; i++) Llink[i]=Rlink[i]=0;
    maxn=0;
    jun.clear();
    Llink[0]=Rlink[0]=Llink[n+1]=Rlink[n+1]=0;
}
inline void shower2() { // 清掉加入的一个值的贡献
    for(int i=jun.size()-1; i>=0; i--) {
        if(!jun[i].dir) Llink[jun[i].plc]=jun[i].val;
        else Rlink[jun[i].plc]=jun[i].val;
    }
    jun.clear();
    maxn=maxn_memo;
}
int main() {
    read(n), read(m);
    for(int i=1; i<=n; i++) {
        read(toola), read(toolb);
        vec.push_back({2,i,toola});
        vec.push_back({3,i,toolb});
    }
    for(int i=1; i<=m; i++) {
        read(toola), read(toolb);
        vec.push_back({1,i,toola});
        vec.push_back({4,i,toolb});
    }
    sort(vec.begin(),vec.end());
    for(int i=0; i<vec.size(); i++) { // 将所有线段的端点重新双射到 0~(2m+2n-1)
        switch(vec[i].opt) {
            case 1:
                A[vec[i].plc]=i;
                break;
            case 2:
                L[vec[i].plc]=i;
                own[i]=vec[i].plc;
                break;
            case 3:
                R[vec[i].plc]=i;
                own[i]=vec[i].plc;
                break;
            default:
                B[vec[i].plc]=i;
                break;
        }
    }
    for(int i=1; i<=m; i++) flc[A[i]/length].push_back({A[i],B[i],i});
    for(int i=0; i<=vec.size()/length+2; i++) {
        shower1();
        int Lbound=i*length,Rbound=(i+1)*length-1;
        if(Rbound>vec.size()-1) Rbound=vec.size()-1;
        sort(flc[i].begin(),flc[i].end());
        for(int j=1; j<=n; j++) if(L[j]<=Lbound and R[j]>=Rbound) ins1(j);
        for(int j=0; j<flc[i].size(); j++) {
            if(flc[i][j].r>=Rbound) continue;
            // 情况 1：块内询问
            maxn_memo=maxn;
            for(int k=Lbound; k<=Rbound; k++) {
                if(!own[k]) continue;
                if(R[own[k]]>=flc[i][j].l and L[own[k]]<=flc[i][j].r) ins2(own[k]);
            }
            ans[flc[i][j].id]=maxn;
            shower2();
        }
        shower1();
        for(int j=1; j<=n; j++) if(L[j]<=Rbound and R[j]>=Rbound) ins1(j);
        int Rpos=Rbound-1;
        for(int j=0; j<flc[i].size(); j++) {
            if(flc[i][j].r<Rbound) continue;
            // 情况 2：跨块询问
            while(Rpos<flc[i][j].r) {
                ++Rpos;
                if(own[Rpos]) ins1(own[Rpos]);
            }
            maxn_memo=maxn;
            for(int k=Rbound; k>=flc[i][j].l; k--) if(own[k] and R[own[k]]>=flc[i][j].l and L[own[k]]<=flc[i][j].r) ins2(own[k]);
            ans[flc[i][j].id]=maxn;
            shower2();
        }
    }
    for(int i=1; i<=m; i++) write(ans[i]), pc('\n');
    return 0;
}

:::

[PA 2011] Kangaroos（复杂回滚莫队） 题解

[PA 2011] Kangaroos（复杂回滚莫队）题解