233
题意：分析：代码：
题意：
有一张
n
∗
m
n*m
n∗m的数字图，矩阵的左上角在
(
1
,
1
)
(1,1)
(1,1)，右下角为
(
x
,
y
)
(x,y)
(x,y)，对于所有的
(
x
,
y
)
(x,y)
(x,y)，求所有矩形中总共有多少个单独的数字
分析：
逆向思维下，我们不去统计每个矩形，而是统计每个数字的贡献，只需要算出这个数字对多少个矩形会产生贡献 建议自己手绘下图哦
x
,
y
1
x,y1
x,y1表示当前需要计算答案的点的坐标，
y
2
y2
y2表示纵坐标的限制 当遇到一个相同的数字
(
i
,
j
)
(i,j)
(i,j)时，上个点能产生贡献的矩形我们分类讨论一下 如果
j
<
y
1
j<y1
j<y1，会产生贡献的矩形就是这样的(红色区域)： 如果
y
1
<
=
j
<
y
2
y1<=j<y2
y1<=j<y2，会产生贡献的矩形就变成了这样的： 答案就用公式算出来就好了 需要注意的是，第二种情况下
(
i
,
j
)
(i,j)
(i,j)显然不会对任何矩形产生贡献，所以
x
,
y
1
x,y1
x,y1不需要更新，在计算
(
x
,
y
1
)
(x,y1)
(x,y1)的贡献时我是将右方的矩形和下方的矩形分开计算的，所以算完右边的就更新下
y
2
y2
y2，下次遇到相同的数字就算下方的
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#define LL long long
#define mo 19900907
using namespace std
;
inline int read() {
int d
=0,f
=1;char s
=getchar();
while(s
<'0'||s
>'9'){if(s
=='-')f
=-1;s
=getchar();}
while(s
>='0'&&s
<='9'){d
=d
*10+s
-'0';s
=getchar();}
return d
*f
;
}
int x
[1210005],Y1
[1210005],Y2
[1210005];
int main()
{
int n
=read(),m
=read(),ans
=0;
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=m
;j
++)
{
int a
=read();
if(!x
[a
]) {x
[a
]=i
;Y1
[a
]=j
;Y2
[a
]=m
+1;continue;}
if(j
<Y1
[a
])
{
(ans
+=(i
-x
[a
])*(Y2
[a
]-Y1
[a
]))%=mo
;
x
[a
]=i
;
Y2
[a
]=Y1
[a
];Y1
[a
]=j
;
continue;
}
if(j
<Y2
[a
])
{
(ans
+=(i
-x
[a
])*(Y2
[a
]-j
))%=mo
;
Y2
[a
]=j
;
}
}
for(int i
=1;i
<=n
*m
;i
++) if(x
[i
]) (ans
+=(n
-x
[i
]+1)*(Y2
[i
]-Y1
[i
]))%=mo
;
cout
<<ans
;
return 0;
}
