[题解]P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories

P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories

可以想到很 naive 的思路，对于每个 \(x\) 值二分答案 \(m\)。check 函数可以 \(O(n)\) 完成。总时间是 \(O(n^2\log n)\) 的。我们发现 check 函数明显还能凹，考虑优化我们对段遍历的过程。

我们可以预处理出 \(a_i\) 之后第一个 \(a_i +1\) 出现的位置，然后就可以使用倍增快速找到 \(x\) 之后第一个合法的 \(x+m-1\) 的位置。寻找 \(x+m-1\) 之后第一个 \(x\) 的位置也不难。如此进行下去，直到进行不下去或者找到 \(k\) 段为止。

这样单次 check 复杂度是 \(O(c\log n)\) 的。其中 \(c\) 是我们总共经过的段数，也即：

\[c=\min(k,\min\limits_{i=x}^{x+m-1} cnt_i) \]

其中 \(cnt_x\) 为 \(x\) 出现的次数。

这样所有查询的 \(c\) 之和一定是 \(O(n)\) 级别的，所以总时间优化到了 \(O(n\log^2 n)\)。

继续优化的话，check 函数已经足够优秀了，考虑对外部的二分进行优化。

不难发现对于所有的 \(x\)，都有 \(ans_x\ge ans_{x-1}\)。

所以其实我们不需要二分，只需要用一个指针，每次从上一个答案 \(-1\) 开始扫描即可。这样 check 的次数是 \(O(n)\) 量级的，于是总时间优化到了 \(O(n\log n)\)。

点击查看代码

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=2e6+5;
int n,k,v,a[N],nxt[22][N];
vector<int> p[N];
inline int get_nxt(int x,int v){auto it=upper_bound(p[v].begin(),p[v].end(),x);return (it==p[v].end()?n+1:*it);
}
inline bool check(int x,int m){//基准记忆为x，m是否可行m--;//从x到x+m-1只需要跳m-1次for(int i=1,u=0;i<=k;i++){u=get_nxt(u,x);for(int j=0;j<=21;j++) if((m>>j)&1) u=nxt[j][u];if(u==n+1) return 0;}return 1;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>k>>v;for(int i=1;i<=n;i++) cin>>a[i],p[a[i]].eb(i);for(int i=1;i<=n;i++) nxt[0][i]=get_nxt(i,a[i]+1),nxt[0][n+1]=n+1;for(int i=1;i<=21;i++) for(int j=1;j<=n+1;j++)nxt[i][j]=nxt[i-1][nxt[i-1][j]];for(int i=1,w=0;i<=v;i++){if(w) w--;while(check(i,w+1)) w++;cout<<w<<" ";}return 0;
}