利用两份递增稀疏坐标表的双指针，线性累加公共坐标的乘积。
OJ: shumeng
题目 ID: CSP202006B
难度:入门
标签:双指针模拟稀疏矩阵
日期: 2026-07-31 16:21
形式化题目
两个 (index, value) 且坐标严格递增。求两个向量的内积
思路
只有两个向量在同一坐标都非零时，才会为内积贡献对应值的乘积。由于两份坐标表都严格递增，可以用双指针像归并一样扫描。
双指针扫描
- 保存第一个向量的全部非零项；
- 顺序读入第二个向量的每一项，不断后移第一个向量的指针，跳过所有坐标更小的项；
- 若坐标相等，累加两个值的乘积。
每个非零项至多被访问一次，因此复杂度只与两个向量的非零项个数有关。因为
先看一个用 map 按坐标查询的朴素实现：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-31 16:21
* update_at: 2026-08-17 22:39
*/
// brute.cpp：小数据暴力解，用映射保存第一个稀疏向量，再逐项查询第二个向量。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, a, b;
cin >> n >> a >> b;
map<int, int> first; // 第一个稀疏向量：坐标 -> 非零值
for (int i = 0; i < a; i++) {
int index, value;
cin >> index >> value;
first[index] = value;
}
// 逐项读入第二个向量，在映射中查询同一坐标是否有非零值
long long answer = 0;
for (int i = 0; i < b; i++) {
int index, value;
cin >> index >> value;
answer += 1LL * first[index] * value; // 映射中不存在的坐标取 0
}
cout << answer << '\n';
return 0;
}代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-31 16:21
* update_at: 2026-08-17 22:39
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXA = 500005;
int n, a, b; // n 为向量维数，a、b 为两个向量的非零项个数
int first_index[MAXA]; // 第一个稀疏向量的坐标
int first_value[MAXA]; // 第一个稀疏向量的非零值
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
for (int i = 0; i < a; i++) cin >> first_index[i] >> first_value[i];
// 双指针扫描：position 指向第一个向量当前项，顺序读入第二个向量的非零项
long long answer = 0;
int position = 0;
for (int i = 0; i < b; i++) {
int second_index, second_value;
cin >> second_index >> second_value;
// 跳过所有坐标比当前项小的第一向量项
while (position < a && first_index[position] < second_index) position++;
// 坐标相同说明两向量在该维度都不为 0，累加对应值的乘积
if (position < a && first_index[position] == second_index) {
answer += 1LL * first_value[position] * second_value;
}
}
cout << answer << '\n';
return 0;
}复杂度
每个非零项至多扫描一次，时间复杂度为
总结
稀疏表示的关键是只处理实际出现的坐标。两个有序稀疏表的公共坐标可以直接用双指针求出，完整维度