Triangular Summation#11863

Triangular Summation (Corrigé)

Auteur du problème :	TheSensei
Préparé par :	Hasan Saleh (MathModel)
Édité par :	Hasan Saleh (MathModel)

Solution

Vous avez une grille $n \times m$ n\times m $A$ . Définissez le coût de la cellule $(i, j)$ comme

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

c'est-à-dire sa valeur multipliée par la distance de Manhattan à la bordure la plus proche. Vous devez répondre à $q$ requêtes, chacune donnant un sous-rectangle $(l_{1}, r_{1})$ (l_1,r_1)– $(l_{2}, r_{2})$ (l_2,r_2). Traitez cette sous-grille comme une nouvelle grille $n^{'} \times m^{'}$ n'\times m' (réindexée de $(1, 1)$ à $(n^{'}, m^{'})$ (n',m')) et calculez la somme de ses coûts.

Le poids

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

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

dépend uniquement des positions $(i^{'}, j^{'})$ (i',j') dans la sous-grille, et non des indices originaux. Nous avons besoin de $\sum A [i] [j] \times w_{i^{'}, j^{'}}$ \sum A[i][j]\times w_{i',j'} sur le rectangle en $O (1)$ par requête.

Utilisez trois structures de somme préfixe :

Somme préfixe 2D standard
$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].
Somme préfixe diagonale
$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]
le long de la diagonale haut-gauche $\to$ bas-droit.
Somme préfixe anti-diagonale
$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]
le long de la diagonale haut-droit $\to$ bas-gauche.

Chaque sous-grille a $⌊ min (n^{'}, m^{'}) /2 ⌋$ \left\lfloor\min(n',m')/2\right\rfloor "couches." Vous pouvez exprimer la somme totale pondérée comme

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

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

où chaque $v_{k}$ v_k est lu en $O (1)$ à partir des trois tables de préfixe.

#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;
        // pour trouver la somme (k varie de 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]
        // donc, je sépare les 4 termes, comme 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;
        // SOLUTION brute force 
        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++

Complexité $O (nm + q)$ \mathcal{O}(nm+q)