牛客小白月赛25 I 十字** 邻接表

链接：https://ac.nowcoder.com/acm/contest/5600/I
来源：牛客网

题目描述
牛牛在玩一个游戏：
一共有n行m列共nm个方格，每个方格中有一个整数。
牛牛选择一个方格，可以得到和这个方格同行、同列的所有数之和的得分。
例如：对于一个22的方格：
1 2
3 4
牛牛选择每个方格的得分如下：
6 7
8 9
因为1+2+3=6，1+2+4=7，1+3+4=8，2+3+4=9。
现在牛牛想知道下一步选择每个格子的得分情况，你可以帮帮他吗？
输入描述:

第一行有两个正整数 和 ，代表方格的行数和列数。
接下来的 行，每行有 个数 aija_{ij}aij​，代表每个方格中的整数。

输出描述:

输出 行 列整数，分别代表选择每个位置方格的得分情况。

示例1
输入
复制

2 2
1 2
3 4

输出
复制

6 7
8 9

备注:

本题输入和输出数据量较大，尽量使用scanf或更快的IO方式~

注意到$n和m$n和m的范围,可能出现$1*1000000$1∗1000000
所以用vector<int> arr[1000000]来存矩阵
用数组$R[i]$R[i]表示第 $i$i行的和
$C[i]$C[i]表示第$i$i列的和
则,第r行c列的行列和为$R[r]+C[c]-mtx[r][c](mtx[r][c]加了两次所以要减掉)$R[r]+C[c]−mtx[r][c](mtx[r][c]加了两次所以要减掉)

#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <unordered_map>
#define MAXN ((int)1e6+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#pragma GCC optimize(2)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \
do { \
	cout << "\033[31;1m " << #x << " -> "; \
	err(x); \
} while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

int n, m, Q, K;

//map<pair<int,int>, int> mp;
//unordered_map<pair<int,int>, int> mp;
ll R[MAXN], C[MAXN];
vector<int> mp[MAXN];

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%d %d ", &n, &m);
	for(int i=1; i<=n; i++)
		for(int k=1, x; k<=m; k++) {
			scanf("%d ", &x);
			R[i] += x;
			C[k] += x;
			mp[i].push_back(x);
		}
	for(int i=1; i<=n; i++) {
		for(int k=1; k<=m; k++) {
			if(k != 1) printf(" "); 
			printf("%lld", R[i]+C[k]-mp[i][k-1]);
		}
		printf("\n");
	}

#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}