Toggle navigation
点码成金编程
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
Home
=>
ProblemSet
=> 3.11-02:开关
Problem1776--3.11-02:开关
1776: 3.11-02:开关
Time Limit:
1
Sec
Memory Limit:
128 MB
Submit:
0
Solved:
3
[
Submit
] [
Status
] [ Creator:
][ 参考程序 ]
Description
现有 n 盏灯排成一排,从左到右依次编号为:1,2,……,n。然后依次执行 m 项操作。
操作分为两种:
指定一个区间 [a,b],然后改变编号在这个区间内的灯的状态(把开着的灯关上,关着的灯打开);
指定一个区间 [a,b],要求你输出这个区间内有多少盏灯是打开的。
灯在初始时都是关着的。
Input
第一行有两个整数 n 和 m,分别表示灯的数目和操作的数目。
接下来有 m 行,每行有三个整数,依次为:c、a、b。其中 c 表示操作的种类。
当 c 的值为 0 时,表示是第一种操作。
当 c 的值为 1 时,表示是第二种操作。
a 和 b 则分别表示了操作区间的左右边界。
Output
每当遇到第二种操作时,输出一行,包含一个整数,表示此时在查询的区间中打开的灯的数目。
Sample Input
Copy
4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4
Sample Output
Copy
1 2
HINT
对于全部的测试点,保证 2≤n≤10
5
,1≤m≤10
5
,1≤a,b≤n,c∈{0,1}。
Source/Category
TJOI2009
算法
模拟
分块
线段树
树状数组