[Usaco2008 Nov]lites 开关灯

Farmer John 为了让奶牛们保持思维敏捷，准备了一个与灯有关的益智玩具。

$N$ 头奶牛依次编号为 $1$ 到 $N$，每头奶牛都站在一盏灯下。傍晚时，所有灯均处于关闭状态。每盏灯由对应的按钮控制，按下第 $i$ 个按钮会切换第 $i$ 盏灯的状态：亮灯变为熄灭，熄灭的灯变为点亮。

奶牛们将执行 $M$ 条指令，每条指令包含一个操作编号以及两个整数 $S_i$ 和 $E_i$。指令分为以下两种：

• 操作编号为 $0$：将编号在 $S_i$ 到 $E_i$ 之间的每个按钮按一次，即切换该区间内所有灯的状态；
• 操作编号为 $1$：询问编号在 $S_i$ 到 $E_i$ 之间共有多少盏灯处于点亮状态。

请帮助 Farmer John 正确回答所有询问。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$，分别表示灯的数量和指令的数量。

接下来 $M$ 行，每行包含三个以空格分隔的整数：操作编号、$S_i$ 和 $E_i$。

输出格式

对于每个操作编号为 $1$ 的询问，输出一行一个整数，表示区间 $[S_i,E_i]$ 内处于点亮状态的灯的数量。

样例输入

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

样例输出

1
2

数据范围

• $2\le N\le 10^5$；
• $1\le M\le 10^5$；
• 操作编号为 $0$ 或 $1$；
• $1\le S_i\le E_i\le N$。

来源与许可

本题为 USACO 2008 November 试题「开关灯」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

1
2