从上到下枚举上下底边,那么涉及两行的添加和删除。

首先预处理出对于每一列,每个位置添加和删除时,是否会对往下$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;
}

  

最新文章

  1. Spring Boot 框架@Temporal(TemporalType.DATE)
  2. Oracle 12c 安装手册
  3. 最简单的C/S程序——让服务器来做加法
  4. MyBatis——Mybatis缓存
  5. How to Calculate difference between two dates in C# z
  6. codeforces 659E . New Reform 强连通
  7. OC--初始化UINavigationController
  8. ecplise最有用的8个快捷键
  9. 老男孩Python全栈开发(92天全)视频教程 自学笔记19
  10. LeetCode(33)-Pascal&#39;s Triangle II
  11. 高效开发 Web 单页应用解决方案
  12. js 获取两个时间戳之间相隔多少天多少小时多少分多少秒
  13. myeclipse使用步骤总结
  14. 转 消息中间件:RocketMQ 介绍(特性、术语、原理、优缺点、消息顺序、消息重复)
  15. [java]给出一个字符串,将重复的字符去除,仅保留第一次出现的字符,且保持去重后的字符在原字符串中的顺序不变
  16. Element ui tree树形控件获取父节点id
  17. MyEclipse安装及破解步骤
  18. phpStrom激活
  19. python基础学习1-描述符
  20. Java基础-DBCP连接池(BasicDataSource类)详解

热门文章

  1. js instanceof 检测某个对象是否是另一个对象的实例
  2. 目标检测算法之R-CNN算法详解
  3. JavaScript编程语言
  4. Android Https双向认证 + GRPC
  5. 修改Tomcat默认连接数
  6. Eclipse中如何打开Map/Reduce Locations窗口
  7. MQ消息队列之MSMQ
  8. P3403 跳楼机
  9. java抽象类详解
  10. Centos安装Samba共享服务器