Triangular Summation#11863

Triangular Summation (Həll təhlili)

Problem Müəllifi:	TheSensei
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Sizdə $n \times m$ n\times m ölçülü bir şəbəkə $A$ var. Hüceyrənin $(i, j)$ qiymətini aşağıdakı kimi müəyyən edin:

C_{i, j} = min (i, n - i + 1, j, m - j + 1) \times A_{i, j},

C_{i,j} \;=\;\min\bigl(i,\;n-i+1,\;j,\;m-j+1\bigr)\times A_{i,j},

yəni, onun dəyəri ilə ən yaxın sərhədin Manhattan məsafəsi. Siz $q$ sorğusuna cavab verməlisiniz, hər biri $(l_{1}, r_{1})$ (l_1,r_1)– $(l_{2}, r_{2})$ (l_2,r_2) alt-dikdörtgenini verir. O alt-şəbəkəni yeni $n^{'} \times m^{'}$ n'\times m' şəbəkə ( $(1, 1)$ -dən $(n^{'}, m^{'})$ (n',m')-ə yenidən indekslənmiş) kimi qəbul edin və onun qiymətlərinin cəmini hesablayın.

Çəki

w_{i^{'}, j^{'}} = min (i^{'}, n^{'} - i^{'} + 1, j^{'}, m^{'} - j^{'} + 1)

w_{i',j'} = \min(i',\,n'-i'+1,\,j',\,m'-j'+1)

yalnız alt-şəbəkədəki $(i^{'}, j^{'})$ (i',j') mövqelərindən asılıdır, orijinal indekslərdən deyil. Biz $\sum A [i] [j] \times w_{i^{'}, j^{'}}$ \sum A[i][j]\times w_{i',j'}-ni $O (1)$ -də sorğu başına hesablamağa ehtiyac var.

Üç prefiks cəmi strukturu istifadə edin:

Standart 2D prefiks cəmi
$p [i] [j] = x \leq i, y \leq j \sum A [x] [y] .$
p[i][j]=\sum_{x\le i,\,y\le j}A[x][y].
Diagonal prefiks
$pd1 [i] [j] = x \leq i, y \leq j \sum p [x] [y]$
\mathrm{pd1}[i][j]=\sum_{x\le i,\,y\le j}p[x][y]
yuxarı-sol $\to$ aşa-sağ boyunca.
Anti-diagonal prefiks
$pd2 [i] [j] = x \leq i, y \geq j \sum p [x] [y]$
\mathrm{pd2}[i][j]=\sum_{x\le i,\,y\ge j}p[x][y]
yuxarı-sağ $\to$ aşa-sol boyunca.

Hər bir alt-şəbəkənin $⌊ min (n^{'}, m^{'}) /2 ⌋$ \left\lfloor\min(n',m')/2\right\rfloor "qat"ı var. Ümumi çəkilmiş cəmi aşağıdakı kimi ifadə edilə bilər:

(v_{1}) - (v_{2}) - (v_{3}) + (v_{4}),

\bigl(v_1\bigr) \;-\;\bigl(v_2\bigr) \;-\;\bigl(v_3\bigr) \;+\;\bigl(v_4\bigr),

burada hər $v_{k}$ v_k üç prefiks cədvəlindən $O (1)$ -də oxunur.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

void solve()
{
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> num(n+1,vector<ll>(m+1));
    for(ll i=1; i<=n; i++) for(ll j=1; j<=m; j++) cin>>num[i][j];
    vector<vector<ll>> p(n+1,vector<ll>(m+1,0));
    for(ll i=1; i<=n; i++) for(ll j=1; j<=m; j++) p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+num[i][j];
    vector<vector<ll>> pd1(n+1,vector<ll>(m+1,0));
    for(ll i=1; i<=n; i++) for(ll j=1; j<=m; j++) pd1[i][j]=pd1[i-1][j-1]+p[i][j];
    vector<vector<ll>> pd2(n+2,vector<ll>(m+2,0));
    for(ll i=1; i<=n; i++) for(ll j=0; j<=m; j++) pd2[i][j]=pd2[i-1][j+1]+p[i][j];
    ll q;
    cin>>q;
    while(q--)
    {
        ll l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        // to find summation (k varies from 0 to floor(min(l2-l1,r2-r1)/2)) p[l2-k][r2-k]-p[l1-1+k][r2-k]-p[l2-k][r1-1+k]+p[l1-1+k][r1-1+k]
        // so, i am seperating the 4 terms, as v1-v2-v3+v4
        ll k = min(l2-l1,r2-r1)/2;
        ll v1 = pd1[l2][r2]-pd1[max((ll)0,l2-k-1)][max((ll)0,r2-k-1)];
        ll v2 = pd2[max((ll)0,l1-1+k)][max((ll)0,r2-k)]-pd2[max((ll)0,l1-2)][max((ll)0,r2+1)];
        ll v3 = pd2[l2][r1-1]-pd2[max((ll)0,l2-k-1)][max((ll)0,r1+k)];
        ll v4 = pd1[max((ll)0,l1+k-1)][max((ll)0,r1+k-1)]-pd1[max((ll)0,l1-2)][max((ll)0,r1-2)];
        ll ans1=v1-v2-v3+v4;
        //bruteforce SOLUTION 
        v1=0;
        v2=0;
        v3=0;
        v4=0;
        while(l1<=l2 && r1<=r2)
        {
            v1+=p[l2][r2];
            v2+=p[l1-1][r2];
            v3+=p[l2][r1-1];
            v4+=p[l1-1][r1-1];
            l1++;
            r1++;
            l2--;
            r2--;
        }
        ll ans2=v1-v2-v3+v4;
        cout<<ans1<<"\n";
    }
} 


int main()
{ 
    IOS;
    int t;cin>>t;
    while(t--){
        solve();
    }
}

C++

Komplekslik $O (nm + q)$ \mathcal{O}(nm+q)