rt

在查询散块时不考虑加法标记的影响也能 AC？

#include<bits/stdc++.h>
#define pb push_back
#define endl '\n'

using namespace std;
typedef long long ll;

const int N=1e5+5,M=998244353;
int n,k,a[N];
int cnt[N];
int dp[N];
inline void mod(int &x)
{
	if (x>=M) x-=M;
	if (x<=-M) x+=M;
}
int pos[N],pre[N];
struct data
{
	int val,pos,dp;
}b[N];
inline bool operator<(data x,data y) { return x.val<y.val; }
inline bool operator<(int x,data y) { return x<y.val; }
const int K=256,B=N/K+5;
int tag[B],sum[N];
int L[B],R[B];
inline void build()
{
	int lxl=(n-1)/K+1;
	for (int i=1;i<=lxl;i++)
	{
		L[i]=R[i-1]+1,R[i]=min(i*K,n);
		for (int j=L[i];j<=R[i];j++) b[j]={0,j,0},pos[j]=i;
	}
	L[1]=0,pos[0]=1,b[0]={0,0,1};
}
inline void udtI(int p,int l,int r,int x)
{
	vector<data> v1,v2;
	for (int i=L[p];i<=R[p];i++)
	{
		if (l<=b[i].pos&&b[i].pos<=r) v1.pb({b[i].val+x,b[i].pos,b[i].dp});
		else v2.pb(b[i]);
	}
	merge(v1.begin(),v1.end(),v2.begin(),v2.end(),b+L[p]);
	sum[L[p]]=b[L[p]].dp;
	for (int i=L[p]+1;i<=R[p];i++)
		mod(sum[i]=sum[i-1]+b[i].dp);
}
inline void udt(int l,int r,int x)
{
	int p=pos[l],q=pos[r];
	if (p==q) udtI(p,l,r,x);
	else
	{
		udtI(p,l,R[p],x);
		udtI(q,L[q],r,x);
		for (int i=p+1;i<q;i++) tag[i]+=x;
	}
}
inline void Udt(int p,int dp)
{
	int q=pos[p];
	for (int i=L[q];i<=R[q];i++)
		if (b[i].pos==p) b[i].dp=dp;
}
inline int qry(int l,int r)
{
	int p=pos[l],q=pos[r],ans=0;
	if (p==q)
	{
		for (int i=L[p];i<=R[p];i++)
			if (l<=b[i].pos&&b[i].pos<=r&&b[i].val<=k) mod(ans+=b[i].dp);
									//应为b[i].val+tag[p]<=k 
	}
	else
	{
		for (int i=L[p];i<=R[p];i++)
			if (l<=b[i].pos&&b[i].pos<=r&&b[i].val<=k) mod(ans+=b[i].dp);
									//应为b[i].val+tag[p]<=k 
		for (int i=L[q];i<=R[q];i++)
			if (l<=b[i].pos&&b[i].pos<=r&&b[i].val<=k) mod(ans+=b[i].dp);
									//应为b[i].val+tag[q]<=k 
		for (int i=p+1;i<q;i++)
		{
			data *it=upper_bound(b+L[i],b+R[i]+1,k-tag[i]);
			if (it!=b+L[i]) mod(ans+=sum[it-b-1]);
		}
	}
	return ans;
}

int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++)
		pre[i]=pos[a[i]],pos[a[i]]=i;
	build();
	*dp=1;
	for (int i=1;i<=n;i++)
	{
		if (pre[i]) udt(pre[pre[i]],pre[i]-1,-1);
		udt(pre[i],i-1,1);
		Udt(i,dp[i]=qry(0,i-1));
	}
	cout<<dp[n]<<endl;
	
	return 0;
}