Triangular Summation#11863

Triangular Summation (Editorial)

Problem Author:	TheSensei
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

You have an $n \times m$ n\times m grid $A$ . Define the cost of cell $(i, j)$ as

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},

i.e. its value times the Manhattan distance to the nearest border. You must answer $q$ queries, each giving a subrectangle $(l_{1}, r_{1})$ (l_1,r_1)– $(l_{2}, r_{2})$ (l_2,r_2). Treat that subgrid as a fresh $n^{'} \times m^{'}$ n'\times m' grid (re-indexed from $(1, 1)$ to $(n^{'}, m^{'})$ (n',m')) and compute the sum of its costs.

The weight

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

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

depends only on positions $(i^{'}, j^{'})$ (i',j') in the subgrid, not on the original indices. We need $\sum A [i] [j] \times w_{i^{'}, j^{'}}$ \sum A[i][j]\times w_{i',j'} over the rectangle in $O (1)$ per query.

Use three prefix-sum structures:

Standard 2D prefix sum
$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 prefix
$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]
along top-left $\to$ bottom-right.
Anti-diagonal prefix
$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]
along top-right $\to$ bottom-left.

Each subgrid has $⌊ min (n^{'}, m^{'}) /2 ⌋$ \left\lfloor\min(n',m')/2\right\rfloor "layers." You can express the total weighted sum as

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

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

where each $v_{k}$ v_k is read off in $O (1)$ from the three prefix tables.

#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++

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