BZOJ5103 : [POI2018]Róznorodno
2024-08-26 05:10:48
从上到下枚举上下底边,那么涉及两行的添加和删除。
首先预处理出对于每一列,每个位置添加和删除时,是否会对往下$k$个里出现这个颜色造成影响。
然后对于每种颜色维护一个长度为$m$的bitset,表示哪些列出现过该颜色。
那么每次修改时,找到前驱和后继,对这一行答案的影响是一段区间加,差分前缀和即可。
时间复杂度$O(\frac{nm^2}{64})$。
#include<cstdio>
typedef unsigned int U;
const int N=3010,M=100010,BUF=72000000;
char Buf[BUF],*buf=Buf;
int n,m,K,lim,i,j,k,u,d,a[N][N],cnt[M],s[N],mx;long long ans;bool in[N][N],ou[N][N];
U f[M][N/32+5];
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void add(U*f,int x){
int y=x>>5,pre=-1,suf=-1;
if(f[y]){
int o=x&31;U z=f[y];
for(int i=o-1;~i;i--)if(z>>i&1){pre=y<<5|i;break;}
for(int i=o+1;i<32;i++)if(z>>i&1){suf=y<<5|i;break;}
}
if(pre<0)for(int i=y-1;~i;i--)if(f[i]){pre=i<<5|(31-__builtin_clz(f[i]));break;}
if(suf<0)for(int i=y+1;i<=lim;i++)if(f[i]){suf=i<<5|__builtin_ctz(f[i]);break;}
int l=max(pre+1,x-K+1),r=min(x,suf-K);
if(l<=r)s[l]++,s[r+1]--;
f[y]^=1U<<(x&31);
}
inline void del(U*f,int x){
int y=x>>5,pre=-1,suf=-1;
f[y]^=1U<<(x&31);
if(f[y]){
int o=x&31;U z=f[y];
for(int i=o-1;~i;i--)if(z>>i&1){pre=y<<5|i;break;}
for(int i=o+1;i<32;i++)if(z>>i&1){suf=y<<5|i;break;}
}
if(pre<0)for(int i=y-1;~i;i--)if(f[i]){pre=i<<5|(31-__builtin_clz(f[i]));break;}
if(suf<0)for(int i=y+1;i<=lim;i++)if(f[i]){suf=i<<5|__builtin_ctz(f[i]);break;}
int l=max(pre+1,x-K+1),r=min(x,suf-K);
if(l<=r)s[l]--,s[r+1]++;
}
int main(){
fread(Buf,1,BUF,stdin);read(n),read(m),read(K);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)read(a[i][j]);
for(j=1;j<=m;j++){
for(d=1;d<K;d++)if(!(cnt[a[d][j]]++))in[d][j]=1;
for(u=0;d<=n;u++,d++){
if(u)if(!(--cnt[a[u][j]]))ou[u][j]=1;
if(!(cnt[a[d][j]]++))in[d][j]=1;
}
for(i=1;i<=n;i++)cnt[a[i][j]]=0;
}
lim=(m+1)>>5;
for(i=1;i<M;i++){
f[i][0]=1;
f[i][(m+1)>>5]|=1U<<((m+1)&31);
}
for(d=1;d<K;d++)for(j=1;j<=m;j++)if(in[d][j])add(f[a[d][j]],j);
for(u=0;d<=n;u++,d++){
if(u)for(j=1;j<=m;j++)if(ou[u][j])del(f[a[u][j]],j);
for(j=1;j<=m;j++)if(in[d][j])add(f[a[d][j]],j);
for(j=1,k=0;j+K-1<=m;j++){
k+=s[j];
if(k>mx)mx=k;
ans+=k;
}
}
return printf("%d %lld",mx,ans),0;
}
最新文章
- Spring Boot 框架@Temporal(TemporalType.DATE)
- Oracle 12c 安装手册
- 最简单的C/S程序——让服务器来做加法
- MyBatis——Mybatis缓存
- How to Calculate difference between two dates in C# z
- codeforces 659E . New Reform 强连通
- OC--初始化UINavigationController
- ecplise最有用的8个快捷键
- 老男孩Python全栈开发(92天全)视频教程 自学笔记19
- LeetCode(33)-Pascal&#39;s Triangle II
- 高效开发 Web 单页应用解决方案
- js 获取两个时间戳之间相隔多少天多少小时多少分多少秒
- myeclipse使用步骤总结
- 转 消息中间件:RocketMQ 介绍(特性、术语、原理、优缺点、消息顺序、消息重复)
- [java]给出一个字符串,将重复的字符去除,仅保留第一次出现的字符,且保持去重后的字符在原字符串中的顺序不变
- Element ui tree树形控件获取父节点id
- MyEclipse安装及破解步骤
- phpStrom激活
- python基础学习1-描述符
- Java基础-DBCP连接池(BasicDataSource类)详解