社区讨论

这是什么逆天错误,求调

CF1129DIsolation参与者 4已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lrbe7fei
此快照首次捕获于
2024/01/13 09:32
2 年前
此快照最后确认于
2024/01/13 12:54
2 年前
查看原帖
rt,读入完了他还读入是个什么东西?
C
#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;
}

回复

8 条回复,欢迎继续交流。

正在加载回复...