正题
题目链接:https://gmoj.net/senior/#contest/show/3146/2
题目大意
一个以左上角为端点的子矩形价值定义为区间内唯一的数的数量，求所有子矩形的权值和。
解题思路
考虑每个数字的贡献，对于相同的数字，产生贡献的右下角一定是一个若干个矩形。我们对于每个数存一个
h
i
,
l
i
,
r
i
h_i,l_i,r_i
hi,li,ri表示上一个有贡献的点的
x
x
x坐标，在
l
i
∼
r
i
l_i\sim r_i
li∼ri范围可以产生贡献。
然后统计即可，时间复杂度
O
(
n
m
)
O(nm)
O(nm)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
const ll N
=1110,XJQ
=19900907;
ll n
,m
,h
[N
*N
],r
[N
*N
],l
[N
*N
],ans
;
int main()
{
scanf("%lld%lld",&n
,&m
);
for(ll i
=1;i
<=n
;i
++){
for(ll j
=1;j
<=m
;j
++){
ll x
;scanf("%lld",&x
);
if(!h
[x
]){h
[x
]=i
;l
[x
]=j
;r
[x
]=m
+1;}
else if(j
<l
[x
]){
(ans
+=(i
-h
[x
])*(r
[x
]-l
[x
])%XJQ
)%=XJQ
;
h
[x
]=i
;r
[x
]=l
[x
];l
[x
]=j
;
}
else if(j
<r
[x
]){
(ans
+=(i
-h
[x
])*(r
[x
]-j
)%XJQ
)%=XJQ
;
r
[x
]=j
;
}
}
}
for(ll i
=1;i
<=n
*m
;i
++)
if(h
[i
])(ans
+=(n
-h
[i
]+1)*(r
[i
]-l
[i
])%XJQ
)%=XJQ
;
printf("%lld",ans
);
}
