矩陣乘法2（codevs3147）

題目描述 Description
給出兩個n*n的矩陣，m次詢問它們的積中給定子矩陣的數值和。

輸入描述 Input Description
第一行兩個正整數n，m。
接下來n行，每行n個非負整數，表示第一個矩陣。
接下來n行，每行n個非負整數，表示第二個矩陣。
接下來m行，每行四個正整數a，b，c，d，表示詢問第一個矩陣與第二個矩陣的積中，
以第a行第b列與第c行第d列為頂點的子矩陣中的元素和。

輸出描述 Output Description
對每次詢問，輸出一行一個整數，表示該次詢問的答案。
樣例輸入 Sample Input
3 2
1 9 8
3 2 0
1 8 3
9 8 4
0 5 15
1 9 6
1 1 3 3
2 3 1 2

樣例輸出 Sample Output
661
388
數據范圍及提示 Data Size & Hint
【數據規模和約定】

對30%的數據滿足，n <= 100。
對100%的數據滿足，n <= 2000，m <= 50000，輸入數據中矩陣元素 < 100，a，b，
c，d <= n。
題解：
這個題雖然名字是矩陣乘法，但是和矩陣快速冪一點關系也沒有。。
30%做法：
直接兩個矩陣暴力相乘，然後再暴力詢問。（ps：集訓隊的題竟然給這麼多暴力分）
100%做法：
如果你對矩陣乘法足夠了解的話，可以發現我們其實可以在O(n)的復雜度內處理出每次詢問。
設要求和的矩陣為A(x1,x2,y1,y2)；第一個矩陣為a，第二個矩陣為b那麼矩陣A可以分行來計算
假設A矩陣第一行(x1)的元素為p[i];
那麼根據矩陣乘法的法則
p[i]等於a矩陣的第X1行的元素和b矩陣的第i列的元素對應相乘，再相加。
sigma{p[i]}（y1<=i<=y2)為a矩陣的第X1行的元素分別和b矩陣的第y1到y2列的元素對應相乘，再相加。
那麼我們可以發現這個式子可以使用乘法結合律提出a矩陣第x1行的元素，再用第i個元素與b矩陣第i列的和相乘，最後把所得的乘積相加，
同理第二行第三行也都一樣，
我們會發現不同行之間也可以提取出b矩陣中每一列的和，
那麼最後所詢問矩陣的和就為a矩陣第x1-x2行每行的元素和與b矩陣第y1-y2列的每列的元素和對應相乘再相加。
所以只要預處理出a矩陣每一行的前綴和
b矩陣每一列的前綴和即可
時間復雜度O(n^2+n*m)；
注意使用scanf或讀入優化。
代碼：

#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)  
#define read(x) scanf("%d",&x); 
int n,m,x,y,xx,yy,aa[2001][2001]={0},bb[2001][2001]={0},a,b;
int main()
{
    read(n);read(m);
    For(i,n) For(j,n)
    {
         read(a);
         aa[i][j]=aa[i-1][j]+a;
    }
    For(i,n) For(j,n)
        {
          read(b);
          bb[i][j]=bb[i][j-1]+b;
        }
     For(i,m)
       {
         read(x);read(y);read(xx);read(yy);
         long long ans=0;
         if (x>xx) swap(x,xx);
         if (y>yy) swap(y,yy); 
         For(j,n)
           ans+=(long long)(aa[xx][j]-aa[x-1][j])*(long long)(bb[j][yy]-bb[j][y-1]);
         printf("%lld\n",ans);
       }
}