这是什么逆天错误,求调
查看原帖
这是什么逆天错误,求调
681036
OldDriverTree楼主2024/1/13 09:32

rt,读入完了他还读入是个什么东西?

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=1e5+1,M=317;
int n,m,a[N],pre[N],last[N];
int block,ans,cnt[N],f[N];
int tax[M][N+N],tag[M];

int belong(int id) { return id/block+1; }
int left(int id) { return (id-1)*block; }
int right(int id) { return id*block-1; }

void insert(int x) {
	int y=belong(x); cnt[x]=-tag[y],ans=(ans+f[x])%mod;
	tax[y][cnt[x]+n]=(tax[y][cnt[x]+n]+f[x])%mod;
}
int update(int x,int v) { int y=belong(x);
	if (cnt[x]+tag[y]<=m) ans=(ans-f[x]+mod)%mod;
	tax[y][n+cnt[x] ]=(tax[y][n+cnt[x] ]-f[x]+mod)%mod;
	cnt[x]+=v;if (cnt[x]+tag[y]<=m) ans=(ans+f[x])%mod;
	tax[y][n+cnt[x] ]=(tax[y][n+cnt[x] ]+f[x])%mod;
}
void change(int l,int r,int x)
{
	int L=belong(l),R=belong(r);
	if (L>=R) {
		for (int i=l;i<=r;i++) update(i,x);
		return;
	}
	for (int i=l;i<=right(L);i++) update(i,x);
	for (int i=left(R);i<=r;i++) update(i,x);
	for (int i=L+1;i<R;i++) {
		if (~x) ans=(ans-tax[i][m-tag[i]+n]+mod)%mod,tag[i]++;
		else tag[i]--,ans=(ans+tax[i][m-tag[i]+n]+mod)%mod;
	}
}
int main()
{
	scanf("%d%d",&n,&m),f[0]=1;
	block=sqrt(n),insert(0);
	for (int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		pre[i]=last[x],last[x]=i;
		change(pre[pre[i] ],pre[i]-1,-1);
		change(pre[i],i-1,1);
		f[i]=ans,insert(i);
	}
	printf("%d",f[n]);
	return 0;
}
2024/1/13 09:32
加载中...