← 返回题目列表

AtCoder · yahoo_procon2019_final_d

D. 危险的跳房子

中文机器翻译题面 查看原题

配点 : 900 点

問題文

N 有若干石头从左到右排成一列。起初,每块石头上都没有任何障碍物,因此可以自由踩上去。

Q 请处理若干查询。 2 种类有,输入形式和查询内容如下。

  • 1 p:从左起 p_i 如果第几块石头上没有障碍物,就放置障碍物;如果已经有障碍物,就移除障碍物。放置了障碍物的石头上无法踩。
  • 2 l r:从左起 l 从第几块石头开始,“1 跳到右边的石头上」「2 重复“跳到右边的石头上”的操作,在不踩到有障碍物的石头的情况下, 从左边到达第 r 块石头的方法总数 求除以 10^9+7 的余数并输出。但是,如果第 l 第 r 块石头上放有障碍物,0 按照...进行。

制約

  • 2 ≤ N ≤ 10^9
  • 1 ≤ Q ≤ 10^5
  • 1 ≤ p ≤ N
  • 1 ≤ l < r ≤ N
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N Q
Query_1
:
Query_Q

出力

2 l r 针对输入格式为...的查询,依查询被给出的顺序分别回答 1 逐行输出。


入力例 1

7 3
2 4 7
1 3
2 1 7

出力例 1

3
3

在第一个查询中,有如下移动方式。

  • 1 向右跳...次,1 向右跳...次,1 向右跳...次。
  • 1 向右跳...次,2 向右跳...次。
  • 2 向右跳...次,1 向右跳...次。

3 在第...个查询中,有如下移动方式。

  • 1 向右跳...次,2 向右跳...次,1 向右跳...次,1 向右跳...次,1 向右跳...次。
  • 1 向右跳...次,2 向右跳...次,1 向右跳...次,2 向右跳...次。
  • 1 向右跳...次,2 向右跳...次,2 向右跳...次,1 向右跳...次。

入力例 2

10 10
2 2 7
1 3
2 2 3
2 1 2
1 5
2 5 8
2 1 6
2 3 4
1 2
2 1 10

出力例 2

8
0
1
0
1
0
0