Problem11398--洛谷P3870 - [TJOI2009] 开关

11398: 洛谷P3870 - [TJOI2009] 开关

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

现有 $n$ 盏灯排成一排,从左到右依次编号为:$1$,$2$,……,$n$。然后依次执行 $m$ 项操作。

操作分为两种:

1. 指定一个区间 $[a,b]$,然后改变编号在这个区间内的灯的状态(把开着的灯关上,关着的灯打开);
2. 指定一个区间 $[a,b]$,要求你输出这个区间内有多少盏灯是打开的。

灯在初始时都是关着的。

Input

第一行有两个整数 $n$ 和 $m$,分别表示灯的数目和操作的数目。

接下来有 $m$ 行,每行有三个整数,依次为:$c$、$a$、$b$。其中 $c$ 表示操作的种类。

- 当 $c$ 的值为 $0$ 时,表示是第一种操作。
- 当 $c$ 的值为 $1$ 时,表示是第二种操作。

$a$ 和 $b$ 则分别表示了操作区间的左右边界。

Output

每当遇到第二种操作时,输出一行,包含一个整数,表示此时在查询的区间中打开的灯的数目。

Constraints

对于全部的测试点,保证 $2\le n\le 10^5$,$1\le m\le 10^5$,$1\le a,b\le n$,$c\in\{0,1\}$。

Sample 1 Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

Sample 1 Output

1
2

HINT

洛谷P3870

EDITORIAL

Source/Category