Codeforces 1129D - Isolation(分块优化 dp)

时间:2023-03-09 07:39:50
Codeforces 1129D - Isolation(分块优化 dp)

Codeforces 题目传送门 & 洛谷题目传送门

又独立切了道 *2900(

首先考虑 \(dp\),\(dp_i\) 表示以 \(i\) 为结尾的划分的方式,那么显然有转移 \(dp_i=\sum\limits_{j=0}^{i-1}dp_j[uni(j+1,i)\le k]\),其中 \(uni(l,r)\) 表示 \([l,r]\) 中出现恰好一次的数的个数。

暴力一脸过不去,考虑优化。我们实时维护一个数组 \(f_j=uni(j+1,i)\),那么上式可写作 \(dp_i=\sum\limits_{j=0}^{i-1}dp_j[f_j\le k]\),而注意到每次 \(i\) 指针的右移引起 \(f\) 数组的变化应为两个区间的 \(+1/-1\),具体来说,我们记 \(pre_v\) 表示 \(v\) 上一次出现的位置,\(pre\_pre_v\) 为 \(v\) 上上次出现的位置,那么指针移到 \(i\) 时 \(f\) 的变化应为 \([pre\_pre_{a_i},pre_{a_i})\) 内的 \(f_j\) 减 \(1\),\([pre_{a_i},i)\) 内的 \(f_j\) 加 \(1\),这个很容易想通。

于是现在问题就转化为,有一个序列,每个元素都有一个权值 \(\text{value}\) 和键值 \(\text{key}\),每次我们可以将一个区间的键值 \(+1/-1\) 或者询问序列中键值 \(\le k\) 的元素的权值之和,注意到这东西既涉及下标又涉及值,是不太好用常规的数据结构,如线段树/平衡树之类维护的,因此考虑硬核数据结构——分块。我们设一个阈值 \(B\) 并将原序列分成 \(B\) 块,并对每一块建一个 BIT,每次我们执行区间 \(+v\) 时,边角块就暴力修改 \(f_i\) 并修改 BIT 里的值,中间块就维护一个标记数组 \(tag_i\) 并令 \(tag_i\) 加上 \(v\),查询时就枚举每一块,并在 BIT 中查询 \(\le k-tag_i\) 所有数的和即可。时间复杂度 \(n\sqrt{n\log n}\),不知道能不能过?

考虑优化,注意到上面的解法并没有用到每次加的值为 \(\pm 1\) 这一性质,所以使用了 BIT 也就多了一个 \(\sqrt{\log n}\) 的复杂度。我们考虑直接对于每一块维护一个前缀和数组 \(sum_{i,j}\) 表示第 \(i\) 块中 \(f_k\le j\) 的 \(dp_k\) 之和,那么由于加的值为 \(\pm 1\),故每次对区间中一个元素暴力加值的时候,最多会引起一个 \(sum_{i,j}\) 的变化,具体来说,如果我们令 \(f_j\) 加上 \(1\),那么对应的 \(sum_{i,f_j}\) 会减去 \(dp_j\);如果我们令 \(f_j\) 减去 \(1\),那么对应的 \(sum_{i,f_j-1}\) 会加上 \(dp_j\);因此修改单个元素的复杂度就变成了 \(\mathcal O(1)\),总复杂度也就变成了 \(n\sqrt{n}\)

还有一个小小的问题,就是当我们计算出 \(dp_i\) 之后,对应的 \(f_i\) 显然是 \(0\),而此时该位置的权值也发生了改变,即由 \(0\) 变为了 \(dp_i\),此时我们就要遍历 \(j\in[0,n]\) 并令 \(sum_{b,j}\) 加上 \(dp_i\),其中 \(b\) 为 \(i\) 所在的块,这样复杂度又会退化到 \(n^2\),这显然是我们所不愿意看到的。不过解决方法非常 simple,我们只需将 \(sum_{i,j}\) 的定义改为第 \(i\) 块中 \(f_k\ge j\) 的 \(dp_k\) 之和,查询时维护一个 \(tot_i\) 表示这块中所有的 \(dp_j\) 之和,拿这块中所有的 \(dp_j\) 之和减去不合法的情况即可,这样修改还是 \(\mathcal O(1)\) 的,不过最后求完 \(dp_i\) 之后的遍历过程就没了,取而代之的是我们只用令 \(sum_{b,0}\) 加上 \(dp_i\),这样复杂度就是货真价实的 \(n\sqrt{n}\) 辣(

代码非常好写,不过似乎有些卡空间(?),而且我的似乎跑得挺快?最慢的一个点才跑了 249ms

const int MAXN=1e5;
const int SQRT=316;
const int MOD=998244353;
void add(int &x,int y){((x+=y)>=MOD)&&(x-=MOD);}
int n,k,a[MAXN+5],blk_sz,blk_cnt,bel[MAXN+5];
int L[SQRT+5],R[SQRT+5],sum[SQRT+5][MAXN+5];
int cnt[MAXN+5],tag[SQRT+5],dp[MAXN+5],tot[SQRT+5];
int pre[MAXN+5],pre_pre[MAXN+5];
void add(int x,int y,int z){
if(x>y) return;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++){
if(z==1) add(sum[bel[x]][++cnt[i]],dp[i]);
else add(sum[bel[x]][cnt[i]--],MOD-dp[i]);
}
} else {
for(int i=x;i<=R[bel[x]];i++){
if(z==1) add(sum[bel[x]][++cnt[i]],dp[i]);
else add(sum[bel[x]][cnt[i]--],MOD-dp[i]);
}
for(int i=L[bel[y]];i<=y;i++){
if(z==1) add(sum[bel[y]][++cnt[i]],dp[i]);
else add(sum[bel[y]][cnt[i]--],MOD-dp[i]);
}
for(int i=bel[x]+1;i<bel[y];i++) tag[i]+=z;
}
}
int calc(){
int ret=0;
for(int i=0;i<=blk_cnt;i++){
add(ret,tot[i]);
if(k-tag[i]+1>=0) add(ret,MOD-sum[i][k-tag[i]+1]);
else add(ret,MOD-tot[i]);
} return ret;
}
int main(){
scanf("%d%d",&n,&k);dp[0]=1;
blk_sz=(int)pow(n,0.5);blk_cnt=n/blk_sz+1;
for(int i=1;i<=blk_cnt;i++){
L[i]=(i-1)*blk_sz;R[i]=min(i*blk_sz-1,n);
for(int j=L[i];j<=R[i];j++) bel[j]=i;
} sum[1][0]=1;tot[1]=1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
add(pre_pre[a[i]],pre[a[i]]-1,-1);add(pre[a[i]],i-1,1);
pre_pre[a[i]]=pre[a[i]];pre[a[i]]=i;dp[i]=calc();
add(sum[bel[i]][0],dp[i]);add(tot[bel[i]],dp[i]);
// printf("%d\n",dp[i]);
} printf("%d\n",dp[n]);
return 0;
}