题目描述
给一个元素均为正整数的矩阵，上升矩阵的定义为矩阵中每行、每列都是严格递增的。
求给定矩阵中上升子矩阵的数量。
输入输出格式
输入格式：
第一行两个正整数n、m，表示矩阵的行数、列数。
接下来n行，每行m个正整数表示矩阵中的元素。
输出格式：
一个数表示数量。
输入输出样例
输入样例#1：
4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
输出样例#1：
100
出题人的题解是O(n3)
感觉可以用单调栈做O(n2)，果真可以
和仓鼠那道比较像
只是需要维护两个tot，一个是只考虑上下单增，另一个tot2同时考虑左右单增，合并时只能用tot2
如果tot>tot2还要给这个节点再加一个
//
// main.cpp
// luoguU4859
//
// Created by Candy on 10/10/16.
// Copyright © 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int n,m,a[N][N];// 0<a[i][j]
struct data{
int l,h;
}st[N];
int top=,tot[N],tot2[N];
ll ans=;
int main(int argc, const char * argv[]) {
n=read();m=read();
memset(a,-,sizeof(a));
for(int i=;i<=n;i++){
top=;
ll cnt=;
for(int j=;j<=m;j++){
a[i][j]=read();
if(a[i][j]<=a[i-][j]) tot[j]=tot2[j]=;
tot[j]++;tot2[j]++;
if(a[i][j]<=a[i][j-]){top=;cnt=;tot2[j]=;} data tmp;
tmp.h=tot2[j];
if(tot[j]==tot2[j]) tmp.l=;
else tmp.l=;
while(top&&st[top].h>=tmp.h){
tmp.l+=st[top].l;
cnt-=st[top].l*st[top].h;
top--;
}
st[++top]=tmp;
cnt+=tmp.l*tmp.h;
if(tot[j]>tot2[j]){
cnt+=*tot[j];
st[++top].h=tot[j];
st[top].l=;
}
ans+=cnt;
//printf("h %d %d %d %d\n",i,j,tot[j],tot2[j]);
//printf("i %d %d %d %d\ncnt %d\n",i,j,tmp.l,tmp.h,cnt);
}
//printf("ans %d\n",ans);
}
printf("%lld",ans);
return ;
}