J - Long Binary String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

長さ 10^{18} の 0, 1 からなる文字列 S があります。S の i 文字目を S_i と表します。

はじめ、S のすべての文字は 0 です。

クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 l r：S_l,S_{l+1},\ldots,S_r を反転する。すなわち、各文字について 0 を 1 に、1 を 0 に変更する。
  • 2 l r：S_l,S_{l+1},\ldots,S_r に含まれる 1 の個数を出力する。

制約

  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq l \leq r \leq 10^{18}
  • 入力される数値はすべて整数

入力

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

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 l r

2 l r

出力

2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

8
2 1 10
1 3 7
2 1 10
1 5 12
2 4 9
2 3 12
1 1 4
2 1 12

出力例 1

0
5
3
7
7

はじめ、S のすべての文字は 0 です。

2 番目のクエリを処理した後、1 である文字は S_3,S_4,S_5,S_6,S_7 です。

4 番目のクエリを処理した後、1 である文字は S_3,S_4,S_8,S_9,S_{10},S_{11},S_{12} です。

入力例 2

6
1 999999999999999998 1000000000000000000
2 999999999999999997 1000000000000000000
1 1 1000000000000000000
2 1 1000000000000000000
2 999999999999999997 1000000000000000000
2 1 1

出力例 2

3
999999999999999997
1
1

Score: 4 points

Problem Statement

There is a string S of length 10^{18} consisting of 0 and 1. Let S_i denote the i-th character of S.

Initially, all characters of S are 0.

Process Q queries. Each query is of one of the following 2 types:

  • 1 l r: Flip S_l,S_{l+1},\ldots,S_r. That is, change each 0 to 1 and each 1 to 0.
  • 2 l r: Print the number of 1s among S_l,S_{l+1},\ldots,S_r.

Constraints

  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq l \leq r \leq 10^{18}
  • All numerical values in the input are integers.

Input

The input is given from Standard Input in the following format:

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 l r

2 l r

Output

Let q be the number of type 2 queries. Print q lines. The j-th line should contain the answer to the j-th type 2 query.

Sample Input 1

8
2 1 10
1 3 7
2 1 10
1 5 12
2 4 9
2 3 12
1 1 4
2 1 12

Sample Output 1

0
5
3
7
7

Initially, all characters of S are 0.

After processing query 2, the characters that are 1 are S_3,S_4,S_5,S_6,S_7.

After processing query 4, the characters that are 1 are S_3,S_4,S_8,S_9,S_{10},S_{11},S_{12}.

Sample Input 2

6
1 999999999999999998 1000000000000000000
2 999999999999999997 1000000000000000000
1 1 1000000000000000000
2 1 1000000000000000000
2 999999999999999997 1000000000000000000
2 1 1

Sample Output 2

3
999999999999999997
1
1