Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1) D. Isolation

题意

给你一个长度为$n$的序列
要你分为若干段，使得每一段不超过$k$个只出现$1$次的数
问方案

题解

$f_i$表示$[1,i]$的答案
然后，对于每一个数字x，记录$last,last1$
表示上次和上上次出现的地方
开一个桶$a$
每一次就把$[last1,last)?1$
然后把$[last,i)$+1
然后每一次，$i$可以从$a_j\le k$的$j$转移
用分块维护这个东西就可以了
具体来说
每个块维护一个前缀和，因为每一次只有$+1/?1$操作，所以只会对前缀和的两个位置产生影响，暴力修改即可
然后我们在块到达右端点的时候再建块，这样前缀和就不会变了
至于还没有建块的元素，最多也是$\sqrt{n}$个，暴力查询/修改就可以了

em…因为我的写法有一点点问题，所以一段的lzy可能为负，但是这个值不超过$\sqrt{n}$，统计前缀和的时候注意一下，不要直到n就好了。。
如果你无脑2*n会MLE
可以通过好点的写法避免这个问题，但是懒得改了

CODE:

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int MOD=998244353;
const int N=100005;
const int NN=350;
int add (int x,int y)	{
    x=x+y;return x>=MOD?x-MOD:x;}
int dec (int x,int y)	{
    x=x-y;return x<0?x+MOD:x;}
int mul (int x,int y)	{
    return (LL)x*y%MOD;}
int n,k;
int a[N];
int bel[N];
int L[N],R[N];
int siz;
int g[NN][N+NN];//第i个块的前缀和
int lzy[N]; 
int f[N],h[N];
int lst[N],lst1[N];//上一次出现的位置 上上次出现的位置
void Init ()
{
    scanf("%d%d",&n,&k);siz=sqrt(n);for (int u=1;u<=n;u++) 	scanf("%d",&a[u]);for (int u=0;u<=n;u++) bel[u]=u/siz+1;for (int u=0;u<=n;u++) R[bel[u]]=u;for (int u=n;u>=0;u--) L[bel[u]]=u;for (int u=1;u<=n;u++) lst[u]=lst1[u]=0;
}
void bt (int x)
{
    for (int u=L[x];u<=R[x];u++)	g[x][h[u]]=add(g[x][h[u]],f[u]);for (int u=1;u<=n+1;u++) g[x][u]=add(g[x][u],g[x][u-1]);
}
void Dec (int l,int r,int x)//对于l,r减1 我们当前的点是x 
{
    for (int u=r;u>=max(L[bel[x]],l);u--)	h[u]--;r=min(r,L[bel[x]]-1);if (r<l) return ;if (bel[l]==bel[r])//在同一个块里面 {
    for (int u=l;u<=r;u++){
    h[u]--;g[bel[l]][h[u]]=add(g[bel[l]][h[u]],f[u]);}return ;}for (int u=bel[l]+1;u<bel[r];u++) lzy[u]--;for (int u=l;u<=R[bel[l]];u++){
    h[u]--;g[bel[l]][h[u]]=add(g[bel[l]][h[u]],f[u]);}for (int u=L[bel[r]];u<=r;u++){
    h[u]--;g[bel[r]][h[u]]=add(g[bel[r]][h[u]],f[u]);}
}
void Add (int l,int r,int x)
{
    	//printf("add:%d %d\n",l,r);for (int u=r;u>=max(L[bel[x]],l);u--)	h[u]++;r=min(r,L[bel[x]]-1);if (r<l) return ;if (bel[l]==bel[r])//在同一个块里面 {
    for (int u=l;u<=r;u++){
    g[bel[l]][h[u]]=dec(g[bel[l]][h[u]],f[u]);h[u]++;}return ;}for (int u=bel[l]+1;u<bel[r];u++) lzy[u]++;for (int u=l;u<=R[bel[l]];u++){
    g[bel[l]][h[u]]=dec(g[bel[l]][h[u]],f[u]);h[u]++;}for (int u=L[bel[r]];u<=r;u++){
    g[bel[r]][h[u]]=dec(g[bel[r]][h[u]],f[u]);h[u]++;}
}
int calc (int x) 
{
    int lalal=0;	for (int u=L[bel[x]];u<x;u++)if (h[u]<=k)lalal=add(lalal,f[u]);for (int u=1;u<bel[x];u++){
    int t=k-lzy[u];if (t<0) continue;if (t>k) printf("GG:%d\n",lzy[u]);lalal=add(lalal,g[u][t]);}return lalal;
}
void solve ()
{
    h[0]=0;f[0]=1;if (0==R[bel[0]]) bt(bel[0]);for (int u=1;u<=n;u++){
    	int x=a[u];if (lst[x]!=0)	Dec(lst1[x],lst[x]-1,u);Add(lst[x],u-1,u);lst1[x]=lst[x];lst[x]=u;f[u]=calc(u);if (u==R[bel[u]])	bt(bel[u]);}printf("%d\n",f[n]);
}
int main()
{
    //freopen("a.in","r",stdin);Init();solve();return 0;
}