题目描述

游游有一个$2$行$L$列的矩阵），矩阵中的每个元素都$\leq 10^9$，她想知道有多少个$2 \times 2$的子矩阵中，$4$个元素恰好有$2$种不同的元素？

由于列数$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$每段的二元组压缩形式。

输入样例

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

输出样例

5

算法

双指针

这道题可以说就是 AtCoder ABC294E 的改编，连样例都一样。思路是类似的，一个指针$i$指向矩阵第一行$a$的首元素，另一个指针$j$指向矩阵第二行$b$的首元素。

还是和之前一样，哪个段的右端点更靠左，就把哪个段往右移动。下面分析一下什么情况下会产生只有两种数值的$2 \times 2$子矩阵：

1. 如果第一行的第$i$段$[l_1,r_1]$与第二行的第$j$段$[l_2,r_2]$值是相同的，那只有可能在边界的时候产生两种值:$(1)$ 若$r_1 \neq r_2$，在右边界处会产生一个仅有两种元素的$2 \times 2$矩阵。$(2)$ 否则$r_1=r_2$，只有在$r_1 \lt L$，且$grid[1][r_1+1]=grid[2][r_2+1]$时才会在右边界处产生一个仅有两种元素的$2 \times 2$矩阵。

2. 如果第一行的第$i$段$[l_1,r_1]$与第二行的第$j$段$[l_2,r_2]$值不相同，且它们的公共段长度$len=min(r_1,r_2)-max(l_1,l_2)+1 \geq 2$，则会产生$len-1$个仅有两种元素的$2 \times 2$矩阵。然后考虑边界：$(1)$ 若$r_1 \lt r_2$，在$grid[1][r_1+1]=grid[2][r_2]$时就会产生一个仅有两种元素的$2 \times 2$矩阵。$(2)$ 同理，若$r_1 \gt r_2$，在$grid[2][r_2+1]=grid[1][r_1]$时就会产生一个仅有两种元素的$2 \times 2$矩阵。$(3)$ 否则$r_1=r_2$，只有在$grid[1][r_1+1]=grid[2][r_2]$且$grid[2][r_2+1]=grid[1][r_1]$时才会在右边界产生一个仅有两种元素的$2 \times 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) {
        int v1 = i1[i].first, v2 = i2[j].first;
        LL l1 = p1, r1 = l1 + i1[i].second - 1;
        LL l2 = p2, r2 = l2 + i2[j].second - 1;
        if(v1 != v2) {
            int len = min(r1, r2) - max(l1, l2) + 1;
            ans += max(0, len - 1);
            if(r1 < r2) {
                p1 += i1[i++].second;
                if(i < n && i1[i].first == v2) ans++;
            }else if(r1 > r2) {
                p2 += i2[j++].second;
                if(j < m && i2[j].first == v1) ans++;
            }else {
                p1 += i1[i++].second;
                p2 += i2[j++].second;
                if(i < n && i1[i].first == v2 && j < m && i2[j].first == v1) ans++;
            }
        }else {
            if(r1 < r2) {
                p1 += i1[i++].second;
            }else if(r1 > r2) {
                p2 += i2[j++].second;
            }else {
                p1 += i1[i++].second;
                p2 += i2[j++].second;
            }
            if(r1 != r2) {
                ans++;
            }else {
                if(i < n && j < m && i1[i].first == i2[j].first) ans++;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}