自动搬运

查看原文

来自洛谷，原作者为

	思考人生中 哼、哼、哼、呃啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

搬运于2025-08-24 22:38:50，当前版本为作者最后更新于2022-06-25 15:23:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

UPD @ 2022-10-05 :修改了一些误导性的内容

赛时的时候在期末复习，就没做。

期末考完来看的时候我的内心 OS 如下：

这不是求个最大不下降子序列就好了吗？这么简单也能评蓝？

然后看到 $n,m,k\le 2\times10^6$ 的时候我凝固了。

好毒瘤一题

以上是我当时不知道 BIT 常数有多小的时候的**言论，大可以忽略。

当然我这个利用在线格式的奇怪做法还是挺有意思的（？

（最终复杂度是与正解差不多的）

正文

我们来看一下题目啊(传送门)

题目要求最小的越过障碍数，那么我们很容能够想到两点：

• 如果没有障碍消失，那么最终越过障碍数就是 $n+m-1$。
• 我们每走过一个消失的障碍，最终越过的障碍数就减少 $1$。

结合这两点我们希望越过尽可能多的消失的障碍。

而越过的障碍，我们用题目中的 $(t_i,x_i)$ 来表示我们在时间 $t_i$ 越过了障碍 $x_i$。

不难发现根据 $d\ge 0$ 有 $\forall t_i<t_j,x_i\le x_j$，于是题目顺利地被转化为求一个最大不下降子序列的。

但是我们就是要走不寻常的路。我们看在线输入的格式。

接下来 $k$ 行，其中第 $i$ 行有两个数字 $t_i, p$。其中 $p$ 用于生成 $x_i$，即： $x_i = \min(x_{i - 1} + p \oplus (lastans \bmod 15) + 1, m)$ 其中 $lastans$ 表示上次变化的答案。

特别地，第一次变化之前 $lastans = 0$， $x_0 = 0$，且当 $x_{i - 1} = m$ 时，将 $x_{i - 1}$ 视作 $0$（注意这不会真的改变 $x_{i - 1}$ 的值）。

同时我们有 $p\le 15$, $(lastans \bmod 15) \le15$， 从而 $p \oplus (lastans \bmod 15) + 1 \le 16$。

那么我们会发现我们得到的 $\left\{ x_i\right\}$ 序列是若干个长度不小于 $\dfrac{m}{\max\{p\}}$ 的严格单调增序列拼接而成的，且每一个的结尾都是 $m$。

利用这个“严格单调增”的性质，我们可以用数组 $a[i]$ 来记录以 $i$ 为开头的最大不下降子序列的后缀最大值（因为 $t_i$ 是按照单调减的顺序给出的）从而只需要在处理完其中某一严格单调增序列 $x_i,x_{i+1}\cdots,x_j$ 时再更新每一个 $a[i]$ 的值，在处理该序列过程中只需要依次更新 $a[x_i],a[x_{i+1}]\cdots,a[x_j]$ 的值，因为前面的值改变并不影响后面的值。

记最大跨过的消失的障碍数为 $ans$。

按照 $t_i$ 相同为一组来处理。设 $t$ 时的 $x$ 值依次为 $x'_1,x'_2\cdots,x'_{tot}$。

那么我们发现当 $x'_i$ 的变化出现的时候，包含 $x'_i$ 的最大不下降子序列为 $a[x'_i]$ 所代表的最大不下降序列前接上 $x'_1,x'_2\cdots,x'_{i}$ ，用这个去更新 $ans$ 即可。

处理完之后我们再用下面的 DP 柿子倒序更新 $a[x'_1],a[x'_2]\cdots,a[x'_{tot}]$:

然后就做完了。主要的复杂度在更新一整个 $a[i]$ 数组，总复杂度为 $O(m\cdot \frac{m}{\frac{m}{\max\{p\}}})=O(m\cdot \max\{p\})$

注意一下在线格式的细节就好了，怕 TLE 就用上快读。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 2000000
using namespace std;

//快读
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}

int a[MAXN+5],tot,stk[MAXN+5],x[MAXN+5],now;
//stk是t时间下的p序列，x是解密以后的x序列

int main() {
    ios::sync_with_stdio(0);
    int n,m,k,t,ans=0,p,lst=0,lstans=0;
    read(n);read(m);read(k);
    read(t);read(p);
    stk[++tot]=p;
    now=t;
    for (int i=1;i<=k;++i) {
        if (i==k) t=p=0;
        else read(t),read(p);
        if (t==now) {
            stk[++tot]=p;
        } else {
            //依次更新并输出答案
            for (int j=1;j<=tot;++j) {
                lst=min(lst+(stk[j]^(lstans%15))+1,m);
                x[j]=lst;
                ans=max(ans,a[lst]+j);
                cout<<n+m-ans-1<<"\n";
                lstans=n+m-ans-1;
            }
            //更新a数组
            ++a[x[tot]];
            for (int j=tot-1;j>=1;--j) a[x[j]]=max(a[x[j+1]],a[x[j]])+1;
            //在处理完后把下一个p放入stk
            stk[tot=1]=p;
            now=t;
            if (lst==m) {
                for (int j=m-1;j>=1;--j) a[j]=max(a[j+1],a[j]);
                lst=0;
            }
        }
    }
    return 0;
}