题解 P6349 【[PA2011]Kangaroos】

feecle6418 · 2020-12-22 15:00:32 · 题解

我们对于询问做莫队。一种简单的错误想法是把 2n 个端点离散化之后拿来莫队，但是假如 l<L，r>R，则询问 [L,R] 是算不到 [l,r] 这个区间的贡献的。也就是，这样无法处理“包含”的情况。

为了能够处理这种情况，我们考虑回滚莫队。把左端点放在所属块上，考虑右端点的位置分类讨论。

• 两端点在同一块（设为 i）：
  • 把包含这一块的区间先加到某个数据结构里，然后不管他们（这些一定有贡献）
  • 剩下的可能产生贡献区间（也就是至少有一端在块内的区间）只有 O(\sqrt n) 个，扫一遍，加到某个数据结构里，更新答案就行
  • 这部分复杂度 O(T(n)q\sqrt n)
• 否则（左端点属于 i，右端点所属 >i）从左往右扫左端点在该块的询问的右端点
  • 把横跨了 i,i+1 两块的区间先加到某个数据结构里，然后不管他们（这些一定有贡献）
  • 剩下的区间不可能包含询问区间了，做普通的回滚莫队即可
  • 这部分复杂度 O(T(n)q\sqrt n)

以上的“某个数据结构”需要在 T(n) 复杂度内支持：

• 加入一个元素
• 询问最大的元素连续段
• 撤销最后几次操作（回滚）

用线段树实现是 O(\log n) 的，其实直接用两个数组 l,r 就可以 O(1) 实现。具体看代码吧：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,Q,bel[200005],ass[200005],tmp[200005],st[1005],ed[1005];
struct Seg{
    int l,r,id;
}t[200005];
struct Thing{
    int x,id;
}a[200005];
struct Query{
    int l,r,id;
};
bool operator <(const Thing i,const Thing j){
    return i.x!=j.x?i.x<j.x:i.id<j.id;
}
vector<Query> q[1005];
int l[200005],r[200005],ans=0,top=0;
struct Oper{
    int c,x,ax,ans;
}S[3000005];
inline void Add(int x){
    if(l[x]||r[x])return ;
    if(!l[x-1]&&!r[x+1])S[++top]={0,x,l[x],ans},S[++top]={1,x,r[x],ans},l[x]=r[x]=x,ans=max(ans,1);
    else if(!l[x-1])S[++top]={0,r[x+1],l[r[x+1]],ans},S[++top]={1,x,r[x],ans},l[r[x+1]]=x,r[x]=r[x+1],ans=max(ans,r[x]-x+1);
    else if(!r[x+1])S[++top]={1,l[x-1],r[l[x-1]],ans},S[++top]={0,x,l[x],ans},r[l[x-1]]=x,l[x]=l[x-1],ans=max(ans,x-l[x]+1);
    else S[++top]={1,l[x-1],r[l[x-1]],ans},S[++top]={0,r[x+1],l[r[x+1]],ans},S[++top]={0,x,l[x],ans},
         l[r[x+1]]=l[x-1],r[l[x-1]]=r[x+1],l[x]=x,ans=max(ans,r[x+1]-l[x-1]+1);
}
void Rollback(int t){
    while(top>t){
        if(!S[top].c)l[S[top].x]=S[top].ax;
        else r[S[top].x]=S[top].ax;
        ans=S[top].ans,top--;
    }
}
void Solve(int id){
    Rollback(0);
    for(int i=1;i<=n;i++)if(t[i].l<st[id]&&t[i].r>ed[id])Add(t[i].id);
    sort(q[id].begin(),q[id].end(),[](Query i,Query j){return i.r<j.r;});
    int tp=top,cur=ed[id];
    for(Query i:q[id]){
        if(i.r>ed[id])continue;
        for(int j=st[id];j<=ed[id];j++)if(i.l<=t[a[j].id].r&&t[a[j].id].l<=i.r)Add(a[j].id);
        ass[i.id]=ans,Rollback(tp);
    }
    Rollback(0);
    for(int i=1;i<=n;i++)if(t[i].l<=ed[id]&&t[i].r>ed[id])Add(t[i].id);
    for(Query i:q[id]){
        if(i.r<=ed[id])continue;
        while(cur<i.r)Add(a[++cur].id);
        tp=top;
        for(int j=ed[id];j>=i.l;j--)Add(a[j].id);
        ass[i.id]=ans,Rollback(tp);
    }
}
int main() {
    scanf("%d%d",&n,&Q);
    for(int i=1,l,r;i<=n;i++)scanf("%d%d",&l,&r),a[i]={l,i},a[i+n]={r,i},t[i]={l,r,i};
    sort(a+1,a+2*n+1);
    for(int i=1;i<=n;i++){
        t[i].l=lower_bound(a+1,a+2*n+1,(Thing){t[i].l,0})-a;
        t[i].r=upper_bound(a+1,a+2*n+1,(Thing){t[i].r,1<<30})-a-1;
    }
    int SQ=sqrt(2*n);
    for(int i=2*n;i>=1;i--)bel[i]=i/SQ+1,st[bel[i]]=i;
    for(int i=1;i<=2*n;i++)ed[bel[i]]=i;
    for(int i=1,l,r;i<=Q;i++){
        scanf("%d%d",&l,&r);
        l=lower_bound(a+1,a+2*n+1,(Thing){l,0})-a;
        r=upper_bound(a+1,a+2*n+1,(Thing){r,1<<30})-a-1;
        q[bel[l]].push_back((Query){l,r,i});
    }
    for(int i=1;i<=bel[2*n];i++)if(q[i].size())Solve(i);
    for(int i=1;i<=Q;i++)printf("%d\n",ass[i]);
    return 0;
}