题目背景

SOURCE：NOIP2016-RZZ-1

题目描述

给出两个 N×N 的矩阵 A、B，矩阵每行每列标号 0～N-1 。
定义这两个矩阵的乘积 AB 为

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKMAAAA+CAYAAABHlKsdAAAGW0lEQVR4nO2dTW6jTBCGX3+agxBlk4UPgTUbLG99A3sTzRYrZ7DsbZSNfYNsrbCJ4BBezCYyN+Hr5s+Agf6hHSBTz4hRQuh2U11UF9Vd7UnEAEEMgP/6bgBBZJAyEoOBlJEYDKSMqoRHzCcTTCYbBPmpOfudndsELQXrCLBh5ZSL/VBIGVWxVnhxHTjOHqcgO/UCl/3zd7ZkJSGOc67QW5ydO7VzhJAyKhPiC0u8LB3st0f2Gz/1hbO7gC1dh4XVR4QoemM1ERmkjKqEn3jHI+zfSzjeOz5Dfu4v8GT13LDxQ8qoClO86cJOh2sP70wbw68zpo9WekHiB07qDnIOW/nVdwPGRnA64+lP8rO9cDHbvuIVUyw+sits7KIIu74aOGLIMirB/MXzFLkRtBdwvT32eILVUoqQJCKk8V3wqdMIrl865xwu+nXlhxv5wlI/mwn/r9/HgSASaJgmBgMpIzEYSBmJwUDKqEg+D23qoNhjDimjItbqDYd8PtkBe5HmEQnlg71NExVIGZXh88o+El3ysH64rt5Rwd5ldRAZpIxa2Njlpm2PmdZQa2NB2liClFEXe4dLNl7vZ5gfQ+UqrCdaP1aEgt6d4OsSH7D2+M/cf/zAyuq5SSOGlLEzfJXOjA3WHBd+tFNY10gUoWG6Myb8R4IjUMZ0efwdBRxsWP3zdMX0WDHgPxJoWbVzOUQOnEhjQYo63/lZd+MSMX1MV+CM/V76oUEZ/YgNPFFhpVQzvht3QO216d/qjpvrY4Uc+zKqRG6455KwNnkb/gypfjNIrTKyIae0Zq+ZqzVoujxZt1fumLpz+fm7SvkbKHak8XsRy9sUKv1mihqfMcDr2oPL8zwEhMdnvC8P8UzC+StsvrCSOWfH0d4zqkXi8/uT1ozGYLij/ygtb1NI9pspbpUxOLF3Qkec7BYe8bye4mX12HJRgNOeeVCVyngCE1BYvp/Bl/Hjmo88Vorz1976GUb0UUreplDsN0M0vE2LPzB4XWPq85iahcaJBJ5PzBR7+btQWbDBA7e8fnM8zvxTnyXNiw8zlqwyf/3cPVogJW9TaPZbZ6rjduwvivwC7hc5B+bBxCUSP6bGiUnqqjjBrc5OUpdOTskgyfzHrg6epLxNod5vZtAIegfYzPZwX1bCjLjwr8ds/QGXfOnUBYfzbPxxRSmYNd7yeRmVbU/qkJe3KXrrtxv1jJ/mZstY+9TwI39y84riMEfVyiXlm+Jw9WWkMvBaQ0PFGGD7Ycoqt9+naj0y8m6XU1aP+P7k+k2+vlIlreG7BmVsEGJc2W1YIX7lrwqn7dqmBjWUGR3pfXRWbBV5iyuLH0ihbKX7TbI+BWrijE0B72ZfpU44db6n8Gm6scpZEFnChzVo1bqRtrlzL6nIW0ZO/Jr075kvW6PQ8v0mV1+h0cI+qg163wafizMLZatZSkbPyjRG8NuHrdqgN69LomN52SFYVDOBYUV5J39olxO3eLmyFBSp3Hj5fpOp76b69j7qPh1oigZ/gj+Vcn5O//PBmQXp46EQyek6qyanODKfp1afuI8Gv1BCyuKVntKeMOUnaiKSU9Gimmijcn0SfSTYa+f+Ma12Z/z6NPl+2oaam5KfS78XqZx6eyBEcrqOdLGs4vMXdq1uawX1afbRwDd+uvpO+X3c3Gj/gfLESvTpJgjkVHKBsms7tFdUn2YfDVwZb/Hdin/S91rI71jSpcGNnPr8bMk+Gp0yXvm+5VTNdAzjCCYYxo9aH1FCljZpZiAOuHzoTdXxrVIe1lNK4kqhbZQ14WsL1x5PT9WfM07mgJe0620KZQfqkC6ncg5v+nnS4RHbvclGjR8appUp5kkbwPURdVrV83Mgy6hIsDGoiEQJsozEYCDLqEi2WSgl6puHlFERa/VhYKPP4rdo6e3v+BMhZewB7neeD5d0B1vanyeDlLETBQsX54fIfG8gTwO9Zt7Zfw5wxp4rbggKenci3X12ESGLzgi/NzBOA51iYRVPJonxtlVb4p+BLKMm3vohtnjbpwsoTGgGUkZNHObz8W1MuFJeXT6JYdp6ZHaxukXI/XZpGBOkjB3I3qz3s3m6hUny9b5R3ZGbT74jRPI91Zzw8x1eZU+bf5a7rBz6yeRJS9n6PMkMxiJpigLo21RL0AwMMRhomCYGAykjMRhIGYnB8D9hzEaw5YtILwAAAABJRU5ErkJggg==" alt="" />

现在要在这两个矩阵上依次进行 Q 次修改操作，两种操作描述如下：

- A i j K ，将 Ai,j 的值修改为 K 。
- B i j K ，将 Bi,j 的值修改为 K 。

在每一次修改操作进行后，输出矩阵 AB（这两个矩阵的乘积矩阵）中每个位置元素的权值之和。

输入格式

第一行，一个正整数 N ，表示矩阵的大小。
接下来 N 行，每行 N 个整数，描述矩阵 A 。
接下来 N 行，每行 N 个整数，描述矩阵 B 。
接下来一行，一个正整数 Q ，表示操作次数。
接下来 Q 行，每行描述一个操作，格式如题面所示。

输出格式

输出 Q 行，每行一个整数，表示这次操作完成后的答案。

样例数据 1

输入

2
1 2
3 4
4 3
2 1
3
A 1 1 2
B 0 1 3
A 0 0 10

输出

40
40
103

备注

【数据规模与约定】

对于 10% 的数据，N = 1。对于 30% 的数据，N,Q≤10。对于 80% 的数据，1≤N≤100，|Ai,j|,|Bi,j|≤10。
对于 100% 的数据，1≤N≤1000，1≤Q≤105，|Aij|,|Bi,j|≤1000。

【题目分析】

　矩阵乘法的答案矩阵中的$(i, j)$为：矩阵$1$的第$i$行中的每个数$(i, k)$，乘上矩阵$2$中第j列的每一个数$(k, j)$

所以要求每次操作的答案，只需要记录一个$sum1[i]$表示矩阵$1$中第$i$列的和，和$sum2[i]$表示矩阵$2$中第$i$行的和，和$sum$表示答案矩阵的和。

修改矩阵$1$中的$(i, j)$时，$sum$只需加上$delta × sum2[i]$

修改矩阵$2$中的$(i, j)$时， $sum$只需加上$delta × sum1[j]$即可。

【CODE】

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int N = ;

ll all, sum1[N], sum2[N];

int a[N][N], b[N][N];

int n, Q;

inline int Re(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline void Wr(ll x){

    if(x < ) putchar('-'), x = -x;

    if(x > ) Wr(x / );

    putchar(x %  + '');

}

int main(){

//    freopen("matrix.in", "r", stdin);

//    freopen("matrix.out", "w", stdout);

    n = Re();

    for(int i = ; i <= n; i++)

        for(int j = ; j <= n; j++)

            a[i][j] = Re(),

            sum1[j] += (ll)a[i][j];

    for(int i = ; i <= n; i++)

        for(int j = ; j <= n; j++)

            b[i][j] = Re(),

            sum2[i] += (ll)b[i][j],

            all += 1LL * sum1[i] * b[i][j];

//    for(int i = 1; i <= n; i++) cout<<sum1[i]<<" "<<sum2[i]<<endl;return 0;

    Q = Re();

    while(Q--){

        char opt;

        scanf("%c", &opt);

        if(opt == 'A'){

            int i = Re() + , j = Re() + , tmp = Re();

            sum1[j] += (tmp - (a[i][j]));

            all += 1LL * (tmp - (a[i][j])) * sum2[j];

            a[i][j] = tmp;

        }

        else if(opt == 'B'){

            int i = Re() + , j = Re() + , tmp = Re();

            sum2[i] += (tmp - (b[i][j]));

            all += 1LL * (tmp - (b[i][j])) * sum1[i];

            b[i][j] = tmp;

        }

        Wr(all), putchar('\n');

    }

    return ;

}

秒客网

【NOIP模拟】matrix（简化矩阵）