题目描述

难度分:$792$

给你两个长度均$L$的数组$a$和$b$（原题是一个$L$列两行的矩阵，一个意思），数组中的每个元素都$\leq 10^9$，输出有多少个下标$i$满足$a[i]=b[i]$。

由于$L(L \leq 10^{12})$很大，输入用一种压缩格式表示，即（元素值，连续出现次数）。

例如$[(10,2),(20,1),(10,3)]$表示数组$[10,10,20,10,10,10]$。数据的输入格式如下：

• 第一行输入$L$，$N_1$和$N_2$分别表示两个数组的长度以及数组$a$的连续段数、数组$b$的连续段数。

• 接下来$N_1$行输入数组$a$每段的二元组压缩形式。

• 再接下来$N_2$行输入数组$b$每段的二元组压缩形式。

输入样例$1$

8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3

输出样例$1$

4

输入样例$2$

10000000000 1 1
1 10000000000
1 10000000000

输出样例$2$

10000000000

输入样例$3$

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

输出样例$3$

28

算法

双指针

指针$i$指向数组$a$的首元素，指针$j$指向数组$b$的首元素，都从第一个元素$pos=1$开始移动。对于每一段，根据区间的游程编码，结合$pos$将其转化为左右端点$[l_i,r_i]$和$[l_j,r_j]$。

1. 如果两个区间的值是不一样的，则谁的右端点更靠左谁往右移动（即$r_i \leq r_j$就右移指针$i$）。
2. 否则计算两个区间的交叠长度$min(r_i,r_j)-max(l_i,l_j)+1$，将其累加到答案上，然后仍然是谁的右端点更靠左谁往右移动。

复杂度分析

时间复杂度

双指针算法遍历的是两个数组的相同值段数，因此时间复杂度为$O(N_1+N_2)$，是线性的。

空间复杂度

需要用两个二元组数组来存储两个数组的游程编码，额外空间复杂度为$O(N_1+N_2)$（其实我感觉这个属于题目输入的数据所占空间，也可以不算在额外空间，额外空间复杂度看成$O(1)$也没什么问题）。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
typedef pair<int, LL> PIL;
LL l;
int n1, n2;

int main() {
    scanf("%lld%d%d", &l, &n1, &n2);
    vector<PIL> i1, i2;
    for(int i = 1; i <= n1; i++) {
        int vi;
        LL li;
        scanf("%d%lld", &vi, &li);
        i1.push_back({vi, li});
    }
    for(int i = 1; i <= n2; i++) {
        int vi;
        LL li;
        scanf("%d%lld", &vi, &li);
        i2.push_back({vi, li});
    }
    LL ans = 0;
    LL p1 = 1, p2 = 1;
    int i = 0, j = 0, n = i1.size(), m = i2.size();
    while(i < n && j < m) {
        LL l1 = p1, r1 = p1 + i1[i].second - 1;
        LL l2 = p2, r2 = p2 + i2[j].second - 1;
        if(i1[i].first != i2[j].first) {
            // 两个区间值不相等
            if(r1 <= r2) {
                p1 += i1[i++].second;
            }else {
                p2 += i2[j++].second;
            }
        }else {
            ans += min(r1, r2) - max(l1, l2) + 1;
            if(r1 <= r2) {
                p1 += i1[i++].second;
            }else {
                p2 += i2[j++].second;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}