题解：P2075 区间 LIS

云浅知处 · 2025-06-09 18:11:40 · 题解

首先，求一个序列 p_1,\cdots,p_n 的 LIS 有一个经典的算法：维护一个集合 S，初始为空，依次扫描 i=1,2,\cdots,n，每次如果 S 中所有数都 <p_i，则令 S\leftarrow S\cup\{p_i\}；否则把 S 中最小的 >p_i 的数变为 p_i。这样最后 |S| 就是 LIS 的长度（注意 S 中的数并不一定构成 LIS）。

这可以解释为，对 j=1,2,\cdots,n 维护了 f_j 表示所有长度为 j 的 LIS 中，最小的结尾元素是多少。初始，所有 f_i=+\infty。那么往末尾添加一个元素 p_i 对 f 的影响就是，如果本来的 f_j<p_i，则存在一个长度为 j+1 的结尾为 p_i 的元素，即我们需要令 f_{j+1}\leftarrow \min(f_{j+1},p_i)。可以发现 f 是递增的，所以只有唯一的那个 f_j<p_i<f_{j+1} 的位置会发生改变，那么造成的影响就和之前说的过程等价了：S 中维护的本质上是所有 f_i<+\infty 的 f_i，每次就是把最小的 >p_i 的元素改成 p_i；如果最大的元素都 <p_i，那么就把 p_i 插入进去。答案自然也就是最大的 i 使得 f_i<+\infty，即 |S|。

现在我们考虑区间询问怎么做，设 S_{l,r} 表示从空集开始，依次按照上述方法插入 p_l,p_{l+1},\cdots,p_r 得到的最终集合。那么，对任意 l<r，我们总有 S_{l+1,r}\subseteq S_{l,r}。证明可以考虑如果当前 A\subseteq B，我们往 A,B 中同时按上述方法加入 x（即，找到第一个 >x 的变成 x，不存在则直接插入）造成的影响。手玩一下可以发现，不论 x 如何取，操作结束后得到的新集合 A',B' 总是仍然满足 A'\subseteq B'。那么对于前面所述的命题，由于初始 S_{l+1,l+1} 肯定是 S_{l,l+1} 的子集，所以对任意的 r>l 都有 S_{l+1,r}\subseteq S_{l,r}。

既然如此，我们要求出 l,r 的答案，就可以这样做：扫描线扫 r=1,2,\cdots,n，对每个 x，它总是在 l 取一段前缀的 S_{l,r} 中出现。我们考虑维护 q_x 表示最大的 l 使得 x\in S_{l,r}，即 x 出现在 S_{1,r},\cdots,S_{q_x,r} 中，不出现在 S_{q_x+1,r},\cdots,S_{r,r} 中。那么对于一次询问 l,r，只需要查询有多少个 x，使得 q_x\ge l。

现在只需要考虑：在 r\to r+1 时，如何维护序列 q，以及如何维护形如「查询全局有多少个 \le l 的元素」这样的询问。

我们先来考虑 r\to r+1 时序列 q 是如何变化的。设 v=p_{r+1}，首先，对任意的 l，不论 S_{l,r} 原先是什么样的，v 总会要么替换掉一个元素，要么直接插入进去，从而出现在 S_{l,r+1} 里，即必然有 q_v=r+1。接下来考虑 q_{v+1}，我们发现 v+1 如果在某个 S_{l,r} 中出现过，那么插入 v 之后必然会被替换掉，所以 q_{v+1} 必然会变成 0。那么 v+2 呢？发现只有当 v+1 出现过的时候才能帮它挡掉这一次操作的影响，否则他也会被替换掉。于是，如果原本序列中 q_{v+2}>q_{v+1}，那么新的 q'_{v+2} 就是原本的 q_{v+1}；否则 q_{v+2} 不变。

以此类推，读者想必已经看出：r\to r+1 造成的影响可以用以下代码描述：（其中代码里的 v=p_{r+1}）

q[v]=r+1,now=0
for(int i=v+1;i<=n;i++)if(q[i]>now)swap(q[i],now)

此时，如果你做过回转寿司，那么这个题的解法已经呼之欲出了。

考虑到这部分也并不算简单，我在这里也详细描述一下这部分是怎么做的。

我们先考虑一个简单的情形：每次操作，我们都是完整地枚举 i 从 1 到 n（而非 v+1 到 n），以及给定初值 now（不一定为 0，尽管本题中总有 now=0，也不可能真的从 1 枚举到 n），然后每次如果 q_i>now，则 \text{swap}(q_i,now)。可以发现，由于我们在查询的时候只关注 \{q_i\}_{i=1}^n 这个可重集（因为只关注多少个 q_x\ge l），而操作对 \{q_i\}_{i=1}^n 这个可重集造成的影响一定恰好是：如果 now 大于 q 的最大值则无事发生，否则就是在可重集中删除最大值，然后插入 now。那么我们可以简单用一个堆来维护。

现在我们的 v 不一定是从 1 开始的，那么考虑分块，每个块维护一个堆表示块内元素的可重集。对于整块，只需要每次把 now 和当前块里的最大值 mx 比较，如果 mx>now，则从当前块中删除 mx，插入 now，然后 now 从这一块出去的时候的新值就是 mx；如果 mx\le now 则无事发生。现在剩下的问题就是，对于散块的部分，该如何快速地知道这个块内的元素 x_1,\cdots,x_B 经历一系列操作 y_1,\cdots,y_k（「经历一个操作 y_i」指的是枚举 j=1,2,\cdots,B，如果 x_j>y_i 则交换二者）后分别变成了多少。注意这里我们必须还原出完整的序列。

我们不妨先来考虑第一个元素 q_1，它经历一系列操作 x_1,\cdots,x_k 之后，如果 q_1>\min x_i，肯定会变成 \min x_i，否则无事发生；然后这一个操作序列 x_1,\cdots,x_k 对 q_2 的影响是什么呢，发现相当于把第一个 <q_1 的 x_i 变成 q_1，然后把 x_i 后面第一个 <x_i 的变为 x_i，以此类推。这是和原本的操作非常对称的一个操作，只不过 chkmax 变成了 chkmin。同理我们发现由于只关注 \min，可以拿一个堆来维护当前的操作序列 x。于是，我们便可以在 O(B\log n) 的时间内重构这个块了。

综上，我们得到一个 O((\frac{n}{B}+B)\log n) 单次操作的算法，取 B=\sqrt{n}，总的复杂度就是 O(n\sqrt{n}\log n+q\log n)。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

#define gc getchar
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=1e5+5;
int a[N],q[N],n,ans[N],m;
vector<pair<int,int> >ques[N];

struct BIT{
    int c[N];
    int lowbit(int x){return x&(-x);}
    void add(int x,int v){x++;for(int i=x;i<=n+1;i+=lowbit(i))c[i]+=v;}
    int sum(int x){int res=0;for(int i=x+1;i;i-=lowbit(i))res+=c[i];return res;}
}T;

const int B=250;
const int NB=N/B+5;

priority_queue<int>P[NB],Q[NB];
int L[NB],R[NB],bl[N];
void rebuild(int p){
    if(Q[p].size()==0)return ;
    int l=L[p],r=R[p];
    for(int i=l;i<=r;i++)if(q[i]>-Q[p].top()){
        int cur=-Q[p].top();
        Q[p].pop(),Q[p].push(-q[i]),q[i]=cur;
    }
    priority_queue<int>().swap(Q[p]);
}

signed main(void){

#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif

    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        ques[r].emplace_back(mk(l,i));
    }

    int S=sqrt(n);memset(L,63,sizeof(L));
    for(int i=1;i<=n;i++)bl[i]=(i-1)/S+1,cmin(L[bl[i]],i),cmax(R[bl[i]],i);
    for(int i=1;i<=bl[n];i++)for(int j=L[i];j<=R[i];j++)P[i].push(0);

    T.add(0,n);
    for(int i=1;i<=n;i++){
        int v=a[i],now=0;

        if(v+1<=n){
            int p=bl[v+1];rebuild(p);
            for(int j=v+1;j<=R[p];j++)if(q[j]>now)swap(now,q[j]);
            priority_queue<int>().swap(P[p]);
            for(int j=L[p];j<=R[p];j++)P[p].push(q[j]);

            for(int j=p+1;j<=bl[n];j++)if(P[j].top()>now){
                int cur=P[j].top();
                P[j].pop(),P[j].push(now),Q[j].push(-now),now=cur;
            }
            T.add(now,-1),T.add(0,1);
        }

        rebuild(bl[v]);
        T.add(q[v],-1),q[v]=i,T.add(q[v],1);
        priority_queue<int>().swap(P[bl[v]]);
        for(int j=L[bl[v]];j<=R[bl[v]];j++)P[bl[v]].push(q[j]);

        for(auto [l,id]:ques[i])ans[id]=T.sum(n)-T.sum(l-1);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';

    return 0;
}