社区讨论
这是什么逆天错误,求调
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 条回复,欢迎继续交流。
正在加载回复...