Problem Statement
We have a sequence of positive integers of length $N^2$, $A=(A_1,\ A_2,\ \dots,\ A_{N^2})$, and a positive integer $S$. For this sequence of positive integers, $A_i=A_{i+N}$ holds for positive integers $i\ (1\leq i \leq N^2-N)$, and only $A_1,\ A_2,\ \dots,\ A_N$ are given as the input.
Find the minimum integer $L$ such that every sequence $B$ of positive integers totaling $S$ is a (not necessarily contiguous) subsequence of the sequence $(A_1,\ A_2,\ \dots,\ A_L)$ of positive integers.
It can be shown that at least one such $L$ exists under the Constraints of this problem.
Constraints
- $1 \leq N \leq 1.5 \times 10^6$
- $1 \leq S \leq \min(N,2 \times 10^5)$
- $1 \leq A_i \leq S$
- For every positive integer $x\ (1\leq x \leq S)$, $(A_1,\ A_2,\ \dots,\ A_N)$ contains at least one occurrence of $x$.
- All values in the input are integers.
有一个明显的 dp,定义 \(dp_i\) 为包含所有何为 \(i\) 的串的最小前缀。枚举一个 \(j\)，那么 \(dp_i=\max_{j<i}nx_{dp_j,i}\) 当中 \(nx_{x,y}\) 表示 \(x\) 后面出现的第一个 \(y\)。 dp 明显是存在单调性的。
考虑数据结构优化，但是没有什么特别适合的数据结构使用。神奇地，考虑CDQ。
如果现在的分支区间为 \([l,r]\)，中心为 \(md\)，那么计算所有 \([l,md]\) 的 DP 值对 \([md+1,r]\) 的 dp 值的贡献。枚举 \(i-j\)，然后发现只有最接近 \(dp_{md}\) 的哪个 \(i-j\) 才是有用的，设他在 \(p\)。只有 $[ls_p,p) $ 这段区间内的数才可以得到贡献，把他对应到 dp 上面就行了。按照 \(p\) 从大到小排序后，用区间覆盖线段树维护 dp 值，然后更新 dp 值即可。
复杂度:\(O(Slog^2n+nlogn)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int S=2e5+5,N=1.5e6+5;
int n,s,a[N];
LL dp[S],tr[S<<2],tag[S<<2];
vector<int>g[S];
struct node{
int l,r,p;
bool operator<(const node&n)const{
return r<n.r;
}
}st[S];
void pushdown(int o,int l,int r)
{
if(~tag[o])
{
tag[o<<1]=tag[o];
tag[o<<1|1]=tag[o];
tr[o<<1]=tag[o];
tr[o<<1|1]=tag[o];
tag[o]=-1;
}
}
void upd(int o,int l,int r,int x,int y,LL z)
{
if(x>y)
return;
if(x<=l&&r<=y)
return tag[o]=tr[o]=z,void();
pushdown(o,l,r);
int md=l+r>>1;
if(md>=x)
upd(o<<1,l,md,x,y,z);
if(md<y)
upd(o<<1|1,md+1,r,x,y,z);
}
LL qry(int o,int l,int r,int x)
{
if(l==r)
return tr[o];
pushdown(o,l,r);
int md=l+r>>1;
if(md>=x)
return qry(o<<1,l,md,x);
return qry(o<<1|1,md+1,r,x);
}
void solve(int l,int r)
{
if(l==r)
return;
int md=l+r>>1,tp=0;
solve(l,md);
upd(1,1,s,l,r,0);
int tmx=(dp[md]-1)%n+1,p=(dp[md]-1)/n;
for(int i=1;i<=r-l;i++)
{
vector<int>::iterator it=upper_bound(g[i].begin(),g[i].end(),tmx);
if(it==g[i].end())
st[++tp]=(node){*(--it),g[i][0]+n-1,i};
else if(it==g[i].begin())
st[++tp]=(node){g[i][g[i].size()-1]-n,g[i][0]-1,i};
else
st[++tp]=(node){*(it-1),(*it)-1,i};
}
sort(st+1,st+tp+1);
for(int i=1;i<=tp;i++)
{
int kl=lower_bound(dp+l,dp+md+1,1LL*p*n+st[i].l)-dp,kr=upper_bound(dp+l,dp+md+1,1LL*p*n+st[i].r)-dp-1;
upd(1,1,s,kl+st[i].p,min(kr+st[i].p,s),st[i].r+1LL*p*n+1);
}
for(int i=md+1;i<=r;i++)
dp[i]=max(dp[i],qry(1,1,s,i));
solve(md+1,r);
}
int main()
{
memset(tag,-1,sizeof(tag));
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i),g[a[i]].push_back(i);
if(!dp[a[i]])
dp[a[i]]=i;
}
solve(1,s);
printf("%lld\n",dp[s]);
}