atcoder#ABC294E. [ABC294E] 2xN Grid

[ABC294E] 2xN Grid

题目描述

2 2 L L 列のマス目があります。 上から i i 行目 (i{1,2}) (i\in\lbrace1,2\rbrace) 、左から j j 列目 (1 j L) (1\leq\ j\leq\ L) のマス目を (i,j) (i,j) で表します。 (i,j) (i,j) には整数 x  i,j x\ _\ {i,j} が書かれています。

x  1,j=x  2,j x\ _\ {1,j}=x\ _\ {2,j} であるような整数 j j の個数を求めてください。

ただし、x  i,j x\ _\ {i,j} の情報は (x  1,1,x  1,2,,x  1,L) (x\ _\ {1,1},x\ _\ {1,2},\ldots,x\ _\ {1,L}) (x  2,1,x  2,2,,x  2,L) (x\ _\ {2,1},x\ _\ {2,2},\ldots,x\ _\ {2,L}) をそれぞれ連長圧縮した、長さ N  1 N\ _\ 1 の列 $ ((v\ _\ {1,1},l\ _\ {1,1}),\ldots,(v\ _\ {1,N\ _\ 1},l\ _\ {1,N\ _\ 1})) $ と長さ N  2 N\ _\ 2 の列 $ ((v\ _\ {2,1},l\ _\ {2,1}),\ldots,(v\ _\ {2,N\ _\ 2},l\ _\ {2,N\ _\ 2})) $ として与えられます。

ここで、列 A A の連長圧縮とは、A A の要素 v  i v\ _\ i と正整数 l  i l\ _\ i の組 (v  i,l  i) (v\ _\ i,l\ _\ i) の列であって、次の操作で得られるものです。

  1. A A を異なる要素が隣り合っている部分で分割する。
  2. 分割した各列 B  1,B  2,,B  k B\ _\ 1,B\ _\ 2,\ldots,B\ _\ k に対して、v  i v\ _\ i B  i B\ _\ i の要素、l  i l\ _\ i B  i B\ _\ i の長さとする。

输入格式

入力は以下の形式で標準入力から与えられる。

L L N  1 N\ _\ 1 N  2 N\ _\ 2 v  1,1 v\ _\ {1,1} l  1,1 l\ _\ {1,1} v  1,2 v\ _\ {1,2} l  1,2 l\ _\ {1,2} \vdots v  1,N  1 v\ _\ {1,N\ _\ 1} l  1,N  1 l\ _\ {1,N\ _\ 1} v  2,1 v\ _\ {2,1} l  2,1 l\ _\ {2,1} v  2,2 v\ _\ {2,2} l  2,2 l\ _\ {2,2} \vdots v  2,N  2 v\ _\ {2,N\ _\ 2} l  2,N  2 l\ _\ {2,N\ _\ 2}

输出格式

答えを 1 1 行で出力せよ。

题目大意

现在有两个长度为 LL 的序列 a,ba,b,找出有多少个下标 ii 满足 ai=bi(1iL)a_i=b_i(1\leq i\leq L)

由于 LL 十分地大,因此 aa 被体现为一个长度为 N1N_1 的二元组序列。下面是二元组序列的生成方式:

  • 对于所有 aa 序列中的 aiai+1a_i\neq a_{i+1},我们在 (i,i+1)(i,i+1) 中间切割一次。
  • 最后 aa 序列会被切割成 N1N_1 块,每一块都是由 lil_i 个相同的数 xix_i 组成的。我们将每一块表示成一个二元组 (xi,li)(x_i,l_i),从左至右拼接起来即可得到一个长度为 N1N_1 的二元组序列。

同理,bb 被体现为一个长度为 N2N_2 的二元组序列。

给出 L,N1,N2L,N_1,N_2 以及两个二元组序列,解决本题开头的问题。

Translated by

https://www.luogu.com.cn/user/399150

8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3
4
10000000000 1 1
1 10000000000
1 10000000000
10000000000
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
380

提示

制約

  • 1 L 10  12 1\leq\ L\leq\ 10\ ^\ {12}
  • 1 N  1,N  2 10  5 1\leq\ N\ _\ 1,N\ _\ 2\leq\ 10\ ^\ 5
  • $ 1\leq\ v\ _\ {i,j}\leq\ 10\ ^\ 9\ (i\in\lbrace1,2\rbrace,1\leq\ j\leq\ N\ _\ i) $
  • $ 1\leq\ l\ _\ {i,j}\leq\ L\ (i\in\lbrace1,2\rbrace,1\leq\ j\leq\ N\ _\ i) $
  • $ v\ _\ {i,j}\neq\ v\ _\ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq\ j\lt\ N\ _\ i) $
  • $ l\ _\ {i,1}+l\ _\ {i,2}+\cdots+l\ _\ {i,N\ _\ i}=L\ (i\in\lbrace1,2\rbrace) $
  • 入力はすべて整数

Sample Explanation 1

マス目は以下の図のようになっています。 ![](https://img.atcoder.jp/abc294/14f38720983c464a322b504738344f24.png) x  1,j=x  2,j x\ _\ {1,j}=x\ _\ {2,j} となるような整数 j j は、j=1,2,5,8 j=1,2,5,8 4 4 つなので、出力すべき値は 4 4 です。

Sample Explanation 2

答えが 32bit 32\operatorname{bit} 整数に収まらない場合があることに注意してください。