题目传送锚点
在博客园食用更佳
前言
对这篇题解有问题或认为这篇题解没写好的同学请先评论或私信我，不要直接举报啊，专栏已经因此封过一次了，不想再被封了，谢谢。
题意
给你三个合法的矩阵 \(A,B,C\)，将它们相乘得到矩阵 \(D\)，求 \(d_{x,y}\) 的值。
思路
首先这道题要用到矩阵乘法，所以没学过矩阵乘法的同学请出门右转，慢走不送。
看到这道题，我们就能想到一个简单的暴力做法，那就是直接乘起来再输出。但是当我们看到 \(1 \le m,n,o,p \le 6 \times 10^3\) 的数据范围和 \(125.00MB\) 的内存限制，会发现这玩意儿根本过不了，所以开始合理优化。
注意到题目只要求输出 \(d_{x,y}\) 的值，并且三个矩阵都是稀疏矩阵，我们可以只求与答案相关的乘积，不然过于浪费空间。为了方便讲解，我们不妨将 \(A \times B\) 得到的矩阵设为 \(Z\)。那么可以得出，\(d_{x,y} = \sum^o_{i=1}z_{x,i} \times c_{i,y}\)。换句话说，我们只需要求出矩阵 \(Z\) 的第 \(x\) 行。
同理，求得矩阵 \(Z\) 的第 \(x\) 行，就只需要矩阵 \(A\) 的第 \(x\) 行和矩阵 \(B\)。
综上，只需要存一下矩阵 \(A\) 的第 \(x\) 行、矩阵 \(B\) 和矩阵 \(C\) 的第 \(y\) 列即可。
于是思路问题就解决了。
代码
远古代码，码风丑陋，不喜勿喷。
#include<bits/stdc++.h>
#define int long long
using namespace std;int x,y,n,m,o,p,k,e,f,te,tf,tk,len,ans,a[6001],bx[6001],by[6001],bz[6001],c[6001];
signed main()
{ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>x>>y>>n>>m>>o>>p;cin>>e>>f>>k;do{if(e==x) a[f]=k;te=e;tf=f;tk=k;cin>>e>>f>>k;}while(e>=te&&(e!=te||f>tf));do{++len;bx[len]=e;by[len]=f;bz[len]=k;te=e,tf=f,tk=k;cin>>e>>f>>k;}while(e>=te&&(e!=te||f>tf));do{if(f==y) c[e]=k;}while(cin>>e>>f>>k);for(int i=1;i<=len;++i) ans+=bz[i]*a[bx[i]]*c[by[i]];cout<<ans;return 0;
}