Triangular Summation#11863

Triangular Summation (Editorial)

Autor del Problema:	TheSensei
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Tienes una cuadrícula de $n \times m$ n\times m $A$ . Define el costo de la celda $(i, j)$ como

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

es decir, su valor multiplicado por la distancia de Manhattan al borde más cercano. Debes responder $q$ consultas, cada una dando un subrectángulo $(l_{1}, r_{1})$ (l_1,r_1)– $(l_{2}, r_{2})$ (l_2,r_2). Trata esa subcuadrícula como una nueva cuadrícula $n^{'} \times m^{'}$ n'\times m' (re-indexada de $(1, 1)$ a $(n^{'}, m^{'})$ (n',m')) y calcula la suma de sus costos.

El peso

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

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

depende solo de las posiciones $(i^{'}, j^{'})$ (i',j') en la subcuadrícula, no de los índices originales. Necesitamos $\sum A [i] [j] \times w_{i^{'}, j^{'}}$ \sum A[i][j]\times w_{i',j'} sobre el rectángulo en $O (1)$ por consulta.

Usa tres estructuras de suma de prefijos:

Suma de prefijos 2D estándar
$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].
Prefijo diagonal
$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]
a lo largo de la diagonal superior izquierda $\to$ inferior derecha.
Prefijo anti-diagonal
$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]
a lo largo de la diagonal superior derecha $\to$ inferior izquierda.

Cada subcuadrícula tiene $⌊ min (n^{'}, m^{'}) /2 ⌋$ \left\lfloor\min(n',m')/2\right\rfloor "capas." Puedes expresar la suma total ponderada como

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

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

donde cada $v_{k}$ v_k se lee en $O (1)$ de las tres tablas de prefijos.

#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;
        // para encontrar la suma (k varía de 0 a 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]
        // así que, estoy separando los 4 términos, como 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;
        // SOLUCIÓN de fuerza bruta 
        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++

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