卡常

 #pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int,int> pi;
int n,m,a[][];
int xx[][];
int t1[],lst[],r;
int ta,sz[];LL ans;
int f1[],dd[],nxt[],mem,sz1[];
inline void read(int &x)
{
x=; int f=; char ch=getchar();
while( (ch<'' || ch>'') && ch!='-') ch=getchar(); if(ch=='-') {f=-; ch=getchar();}
while(ch>='' && ch <='') x=x*+ch-'',ch=getchar();
x*=f;
}
int main()
{
int i,j,k,t,p;
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
read(a[i][j]);
a[i][j]^=;
if(a[i][j]==)
{
for(k=i;k>=;k--)
{
if(xx[k][j]) break;
xx[k][j]=i;
}
}
}
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
if(xx[i][j]==)
xx[i][j]=n+;
xx[i][j]-=i;
}
// for(i=1;i<=n;i++)
// {
// for(j=1;j<=m;j++)
// printf("%lld ",xx[i][j]);
// puts("");
// }
// return 0;
for(i=;i<=n;i++)
{
r=;
for(j=m;j>=;j--)
{
while(r&&xx[i][t1[r]]>xx[i][j]) lst[t1[r]]=j,r--;
t1[++r]=j;
}
while(r) lst[t1[r]]=,r--;
mem=;
for(j=;j<=m;j++) sz1[j]=,f1[j]=;
for(j=;j<=m;j++)
if(lst[j]!=)
dd[++mem]=j,nxt[mem]=f1[lst[j]],f1[lst[j]]=mem,sz1[lst[j]]++;
for(j=;j<=m;j++) sz[j]=;
for(j=m;j>=;j--) sz[j]+=sz1[j],sz[lst[j]]+=sz[j];
//for(j=1;j<=m;j++) printf("%lld ",lst[j]);
//puts("");
ta=;t=0x3f3f3f3f;
for(j=;j<=m;j++) t=min(t,xx[i][j]),ta+=t;
for(j=;j<=m;j++)
{
ans+=ta;
for(k=f1[j];k;k=nxt[k])
{
p=dd[k];
ta+=(sz[p]+)*(xx[i][p]-xx[i][lst[p]]);
}
ta-=xx[i][j];
}
}
printf("%lld",ans);
return ;
}

最新文章

  1. [No00006F]总结C#获取当前路径的各种方法
  2. AndroidManifest.xml详解(上)
  3. LightOJ 1234 Harmonic Number
  4. RTC实时时钟
  5. JavaScript重复元素处理
  6. Window 10通过网线和Wifi连接树莓派
  7. rac安装grid报INS-41112错误
  8. RabbitMq install on Centos6.3
  9. git分支--branch
  10. Stochastic Gradient Descent
  11. socket编程: TypeError: must be bytes or buffer, not str
  12. logstash安装及基础入门
  13. leetcode 131. Palindrome Partitioning 、132. Palindrome Partitioning II
  14. 535 5.7.8 Error: authentication failed: generic failure安装EMOS时SMTP测试报错
  15. 趣味工具figlet
  16. mysql 触发器(Trigger)简明总结和使用实例
  17. Python itertools.combinations 和 itertools.permutations 等价代码实现
  18. [HAOI2017模拟]囚人的旋律
  19. Linux 软件看门狗 watchdog 喂狗
  20. LINUX中的DNS服务---高速缓存DNS

热门文章

  1. 翻译:A Tutorial on the Device Tree (Zynq) -- Part IV
  2. openwrt - squashfs-sysupgrade.bin 的生成过程
  3. 树莓派wiringPi经常使用的函数介绍
  4. linux学习:进程间通信—管道
  5. MongoDB and Redis
  6. android 提示
  7. div 下 的img水平居中
  8. iOS 声明属性关键字的总结
  9. Dedecms(织梦)文章内容页和图片集内容页,调用缩略图的方法
  10. BZOJ_5311_贞鱼_决策单调性+带权二分