\(A=(a _ 1,\ldots,a _ l)\) を連長圧縮した列 \(\widetilde{A}=(x _ i,l _ i) _ {1\leq i\leq n}\) に対して、\(I _ A=(I _ {A,i}) _ {0\leq i\leq n}=\left(\displaystyle\sum _ {1\leq j\leq i}l _ j\right) _ {0\leq i\leq n}\) と定めます。 すると、\(j=1,2,\ldots,n\) に対して、\(I _ {A,j-1}\lt i\leq I _ {A,j}\) を満たす \(i\) に対する \(a _ i\) の値はすべて等しいです。

\(1,2\) 行めの数列を表す列 \(R _ 1,R _ 2\) に対して、\(I _ {R _ 1},I _ {R _ 2}\) をマージしたソート済み列を \(I=(I _ 0,\ldots,I _ {N _ 1+N _ 2+1})\) とします。 このとき、\(j=1,2,\ldots N _ 1+N _ 2+1\) に対して、\(I _ {j-1}\lt i\leq I _ j\) を満たす \(i\) に対する \((R _ {1,i},R _ {2,i})\) の値はすべて等しいです。

よって、各 \(I _ j\) に対して、\(R _ {1,I _ j}=R _ {2,I _ j}\) のときに答えに \(I _ j-I _ {j-1}\) を加えることでこの問題を解くことができました。

時間計算量は \(O(N _ 1+N _ 2)\) です。

実装例は以下のようになります。 以下の実装では、非負整数 \(i,j\) について、\(i=j\iff i\operatorname{xor}j=0\) が成り立つことを利用しています。

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

int main() {
    using namespace std;

    unsigned long L;
    unsigned N, M;
    cin >> L >> N >> M;

    vector<pair<unsigned long, unsigned>> A(N), B(M);
    for (auto&&[l, v] : A)
        cin >> v >> l;
    for (auto&&[l, v] : B)
        cin >> v >> l;
    A.emplace(begin(A));
    B.emplace(begin(B));

    for (unsigned i{}; i < N; ++i) {
        A[i + 1].first += A[i].first;
        A[i].second ^= A[i + 1].second;
    }
    for (unsigned i{}; i < M; ++i) {
        B[i + 1].first += B[i].first;
        B[i].second ^= B[i + 1].second;
    }

    vector<pair<unsigned long, unsigned>> C(N + M + 2);
    merge(begin(A), end(A), begin(B), end(B), begin(C));

    for (unsigned i{}; i < N + M + 1; ++i) {
        C[i].first = C[i + 1].first - C[i].first;
        C[i + 1].second ^= C[i].second;
    }
    C.pop_back();

    unsigned long ans{};
    for (const auto&[l, c] : C)
        if (c == 0)
            ans += l;

    cout << ans << endl;

    return 0;
}