自动搬运

查看原文

来自洛谷，原作者为

	minstdfx Believe in the beauty of life, maintain an optimistic attitude, and know that ... is always invincible

搬运于2025-08-24 22:36:12，当前版本为作者最后更新于2022-02-09 18:40:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不要在意我用讲评的稿子来糊题解

不要吐槽退役选手整出来的非常不专业的讲稿

“那么，跳过中场休息，我们来讲最后一题。”

0x00 题意观察

• 给定两个序列，值域在 $[1,m]$。
• $B$ 是一个排列，$A$ 长度为 $n$。
• 多次询问，每次询问 $A$ 的一个子区间，在子区间里找到最长的一个子序列，使得它是 $B$ 的子串。

那么很显然第一下我们要做的就是按照给定的 $B$ 重新编号，使得 $A$ 中任意两个元素在 $B$ 中的相对位置不变，同时使得 $B$ 变为升序。

换句话说，把 $A$ 中的所有数换成 $B$ 中它的下标。

这样的话，问题转化为在 $A$ 的子区间内找最长子序列，使得它是连续的一段递增整数。

举个例子：
$\text{\tt\textcolor{blue}{B}:\textcolor{blue}{1 2 5 4 3}}$
$\text{\tt\textcolor{red}{A}:\textcolor{red}{4 2 5 1 4 2 3}}$
变换后：
$\text{\tt\textcolor{purple}{A}:\textcolor{purple}{4 2 3 1 4 2 5}}$

0x01 解题思路

前注：下文中 dp 代表「动态规划算法」时不使用 $\LaTeX$，代表「代码中的数组」时使用。

考虑暴力每次以 $O(l)$ 复杂度当做 dp 做，其中 $l$ 为当前询问区间长度。

从左往右进行动态规划，记 $ls_i$ 代表 dp 到当前位置的时候值 $i$ 最后一次出现的位置。

for(int i = 1; i <= n; ++i){
    dp[i] = dp[ls[a[i] − 1]] + 1;
    ans = max(ans, dp[i]);
    ls[a[i]] = i;
}

复杂度 $O(qn)$。可惜没有部分分现在有了，期望得分 10。

一看题目其实是个莫队板子，只是在线，但是有离线部分分，期望得分 40（加上暴力）。

---

考虑一种特殊的分块，求出每个可能的“完整块区间”（即整块）的答案，对于不在完整块中的部分，类比莫队，向左向右扩展区间，那么向左向右都只会最多扩展一个区间长度。显然如果预处理得当复杂度可以接受 （然而要卡常）。

稍稍考虑一下这个过程，首先处理出：

• $bel_i$：每个位置所属的块
• $pans_{l,r}$：两个完整块之间的答案
• $ls_i$：$i$ 左边离它最近的值为 $a_i-1$ 的下标
• $rs_i$：$i$ 右边离它最近的值为 $a_i+1$ 的下标

对于区间没有包含完整块的直接暴力（显然长度最大也就两倍块长）。代码就不放了，和前面的暴力没区别。

包含完整块的，取最接近它的整块子区间然后扩展。
先挪动右端点，考虑右边增加的元素可能的贡献。贡献来自两处:

• 以完整块中元素为末端点的区间
• 以右端点挪动经过的元素为末端点的区间

（有不理解的可以考虑 dp 的过程，本质上是考虑“如果暴力 dp 到这一位了会怎么更新”）

对于第二种，直接在向右扩展时顺便记录一下即可，做起来非常容易，就不细讲了。

---

memset(tmp, 0, sizeof(int) * (m + 1));
for(int i = 1; i <= n; ++i)
    ls[i] = tmp[a[i] − 1], tmp[a[i]] = i;
memset(tmp, 0, sizeof(int) * (m+1));
for(int i = n; i >= 1; −−i)
    rs[i] = tmp[a[i] + 1], tmp[a[i]] = i;
for(int l = 1; l <= n; l += blsize) //prel 的处理 
{
    ans = 0;
    int *const dp = predp[bel[l]];
    memset(dp, 0, sizeof(int) * (n + 1)); //清空
    for(int r = l; r <= n; ++ r)
    {
        dp[r] = dp[ls[r]] + 1;
        ans < dp[r] ? ans = dp[r] : 114514; //（
        if(r == n || bel[r] != bel[r + 1])
        //dp 到末尾了记一下
        blkans[bel[l]][bel[r]] = ans;
    }
}

---

那么对于第一种呢？靠现有的东西基本没法维护。
如果暴力，那么这一段是一个暴力 dp 的收尾工作，考虑能不能直接跳过前面的 dp 阶段直接处理这一小段的贡献。

发现可以。

注意到这一段 dp 过程中的左端点一定是某个块的左端点。
维护 $prel_{bl,r}$ 代表对从第 $bl$ 个块的左端点到数列末尾这个区间进行 dp 时的 $dp$ 数组。
即，左端点在第 $bl$ 个块开头或后边，以 $r$ 结尾的最长满足条件序列长度。

同理，维护 $prer_{bl,l}$ 代表左端点为 $l$，右端点在第 $bl$ 个块末尾或前边的最长满足条件序列长度。

方便起见，我们反过来维护 $dp$ 数组。 维护一个 $f_i$ 代表当前区间内，反向的 $dp$ 数组，即在当前区间内以 $i$ 值开头的最长满足要求的子序列。
每当在右边插入一个数，考虑它对左边的所有数 $f_i$ 的影响。 根据定义，对于每个 $i$，有：

$$f(a_i+1-prel_{bel(l),i})=\max\{f(a_i+1-prel_{bel(l),i}),prel_{bel(l),i}\} $$

这个好理解，用预处理出来的信息去维护当前区间的 $f$。

也就是说，向右扩展时，我们发现贡献来自两处：

• 整块到右散块的贡献；
• 右散块中一个元素到另一个元素的贡献。

那么向左移动区间的过程呢？同理。注意要考虑左边扩张的区间和右边已经扩张的非完整块部分一起造成影响。
我们发现贡献来自三处：

• 左散块到整块的贡献；
• 左散块中一个元素到另一个元素的贡献。
• 左散块到右散块的贡献。

$$f(a_i)=\max\{f(a_i),f(a_i+1)+1,prer_{bel(r),i}\}$$

分别对应三种贡献，很好理解。

0x02 注意事项&复杂度分析

• 注意如果两个 $n\sqrt n$ 长度的预处理数组分开开会 MLE。考虑开在一起，由于 prel[bl+1] 与 prer[bl] 的第二维下标不重合，可以据此压缩。
• 注意撤销操作不能直接 memset 哦，会挂 TLE 的。
• 安排一个快速的 IO，并且不要轻易刷新缓冲区，无论是加速过的 iostream 还是带刷新的模板。

复杂度：
时间 $O((n+q)\sqrt n)$ （块长取 $\sqrt n$）。
空间 $O(n\sqrt n)$。

0x03 引用资料

无。

各位可以在月赛讲评页面下载到讲稿。

验题代码：

#include <bits/stdc++.h>
#include "wdoi-fastio.hpp" // 省略头文件
#define cin fio
#define cout fio
#define endl _fios::endl
fast_iostream<> fio;
using namespace std;
const int maxn=3e5+4,maxsqrtn=1304;
int n,m,q;// as given.
int a[maxn],b[maxn],p[maxn];// as above.
// the array p will be used over and over again./tyt
int ans;// lastans
int ql,qr;// l and r for each query
int blsize;// size of blocks
int *const tmp=p;//别名（逃
int ls[maxn],rs[maxn];
int blkans[maxsqrtn][maxsqrtn],bel[maxn];//分块基操
int predp[maxsqrtn][maxn];//prel,prer
inline int max(int a,int b) { return a<b?b:a; } 

int main()
{
    cin>>m>>n>>q;
    blsize=sqrt(n)*0.8;
    for(register int i=1;i<=m;++i) cin>>b[i],p[b[i]]=i;
    for(register int i=1;i<=n;++i) cin>>a[i],a[i]=p[a[i]];
    for(int i=1;i<=n;++i)
        bel[i]=(i-1)/blsize+1;
    // 2nk+2ql, k=Number of blocks, l = length of each block
    memset(tmp,0,sizeof(int)*(m+1));
    for(int i=1;i<=n;++i)
        ls[i]=tmp[a[i]-1],tmp[a[i]]=i;
    memset(tmp,0,sizeof(int)*(m+1));
    for(int i=n;i>=1;--i)
        rs[i]=tmp[a[i]+1],tmp[a[i]]=i;
    for(int l=1;l<=n;l+=blsize)// prel的处理
    {
        ans=0;
        int *const dp=predp[bel[l]];
        memset(dp,0,sizeof(int)*(n+1));//清空
        for(int r=l;r<=n;++r)
        {
            dp[r]=dp[ls[r]]+1;
            ans<dp[r]?ans=dp[r]:114514;//不要在意（
            if(r==n || bel[r]!=bel[r+1]) //dp到末尾了记一下
                blkans[bel[l]][bel[r]]=ans;
        }
    }
    for(int i=1;i+blsize-1<=n;i+=blsize)
    {
        int r=i+blsize-1;//prer
        int *const dp=predp[bel[r]+1];
        //不能简单的直接使用dp数组并清空，否则会影响到前面的prel
        //当然你算好了哪些是prer哪些是prel也行
        //注意一下，本来求的是prer[bl][i]
        //这里存在predp[bl+1][i]的目的是防止重叠
        //当然由于小于两个块长时暴力所以你写predp[bl][i]也没关系
        //但是这样不好（
        //我一开始验题的时候就是这么写的，现在重构还是得改改
        memset(p,0,sizeof(int)*(n+1));
        for(int l=r;l;--l)
            p[l]=p[rs[l]]+1;
        for(int l=r;l;--l)
            dp[l]=p[l];//同理的dp
    }
    ans=0;
    memset(p,0,sizeof(p));//清一清
    int *const dp=p;
    while(q--)
    {
        cin>>ql>>qr;
        ql^=ans,qr^=ans;
        int lbel=bel[ql]+1,rbel=bel[qr]-1;
        if(lbel<=rbel)//扩展答案
        {
            ans=blkans[lbel][rbel];
            for(int i=rbel*blsize+1;i<=qr;++i)//move right bound
                ans=max(ans,dp[a[i]+1-predp[lbel][i]]=max(dp[a[i]+1-predp[lbel][i]],predp[lbel][i])); 
            for(int i=(lbel*blsize-blsize);i>=ql;--i)//move left bound
            {
                ans=max(ans,dp[a[i]]=max(dp[a[i]],
                    max(
                        predp[rbel+1][i],
                        dp[a[i]+1]+1
                    )
                ));
            }
            //注意直接memset清空会T
            for(int i=rbel*blsize+1;i<=qr;++i) dp[a[i]+1-predp[lbel][i]]=0;
            for(int i=(lbel*blsize-blsize);i>=ql;--i) dp[a[i]]=0;
            cout<<ans<<"\n";//别endl
        }
        else //暴力
        {
            ans=0;
            for(int i=ql;i<=qr;++i)
                if(dp[a[i]]<dp[a[i]-1]+1)
                    dp[a[i]]=max(dp[a[i]],dp[a[i]-1]+1),
                    ans=max(ans,dp[a[i]]);
            for(int i=ql;i<=qr;++i) dp[a[i]]=0;
            // 注意撤销操作不能直接memset哦，会挂的
            cout<<ans<<"\n";
        }
    }
    fio.flush();
    return 0;
}