正題

題目鏈接:https://gmoj.net/senior/#contest/show/3146/2

---

題目大意

一個以左上角為端點的子矩形價值定義為區間內唯一的數的數量，求所有子矩形的權值和。

---

解題思路

考慮每個數字的貢獻，對于相同的數字，產生貢獻的右下角一定是一個若干個矩形。我們對于每個數存一個$h_i,l_i,r_i$表示上一個有貢獻的點的$x$坐標，在$l_i～r_i$范圍可以產生貢獻。

然后統計即可，時間復雜度$O(nm)$

---

$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); }

總結

以上是生活随笔為你收集整理的jzoj1282-资源勘探【统计】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。