Triangular Summation#11863

Triangular Summation (Розбір)

Автор проблеми:	TheSensei
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Рішення

У вас є сітка $n \times m$ n\times m $A$ . Визначте вартість клітинки $(i, j)$ як

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

тобто її значення помножене на манхеттенську відстань до найближчого краю. Вам потрібно відповісти на $q$ запитів, кожен з яких дає підпрямок $(l_{1}, r_{1})$ (l_1,r_1)– $(l_{2}, r_{2})$ (l_2,r_2). Розглядайте цю підсітку як нову сітку $n^{'} \times m^{'}$ n'\times m' (перенумеровану з $(1, 1)$ до $(n^{'}, m^{'})$ (n',m')) та обчисліть суму її вартостей.

Вага

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

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

залежить лише від позицій $(i^{'}, j^{'})$ (i',j') у підсітці, а не від оригінальних індексів. Нам потрібно $\sum A [i] [j] \times w_{i^{'}, j^{'}}$ \sum A[i][j]\times w_{i',j'} по прямокутнику за $O (1)$ на запит.

Використовуйте три структури префіксних сум:

Стандартна 2D префіксна сума
$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].
Діагональна префіксна сума
$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]
вздовж верхнього лівого $\to$ нижнього правого.
Антидіагональна префіксна сума
$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]
вздовж верхнього правого $\to$ нижнього лівого.

Кожна підсітка має $⌊ min (n^{'}, m^{'}) /2 ⌋$ \left\lfloor\min(n',m')/2\right\rfloor "шарів." Ви можете виразити загальну зважену суму як

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

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

де кожен $v_{k}$ v_k читається за $O (1)$ з трьох префіксних таблиць.

#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;
        // щоб знайти суму (k змінюється від 0 до 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]
        // отже, я розділяю 4 терміни, як 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;
        //брутфорс РІШЕННЯ 
        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++

Складність $O (nm + q)$ \mathcal{O}(nm+q)