P8120 「RdOI R3.5」RMSQ 题解

· · 题解

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

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

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

0x00 题意观察

那么很显然第一下我们要做的就是按照给定的 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（加上暴力）。

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

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

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

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

（有不理解的可以考虑 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。

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

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

复杂度：
时间 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;
}