做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2276. -- 树状的灯

2276: 树状的灯

时间限制: 1 Sec  内存限制: 128 MB
提交: 147  解决: 50
[上一题][提交][讨论版][状态][下一题]

题目描述

校园里有一个古老的树,树上挂着n盏灯。这些灯围成了树的形状,很好看。现在,这n盏灯,有的的开着的,有的是关着的。开着用1来表示,关着用0来表示。当这些灯形成一个完美组合时,会非常非常好看。为了让这个树状的灯形成完美组合,小明打算对这些灯进行m个操作。小明可以对这些灯中的某些连续的灯进行关灯、开灯或者取反(开的灯关;关的灯开)操作,也可以数一下有多少盏灯是开着的,多少盏灯是关着的。请把数灯的结果输出来。

输入

第一行:输入一个正整数n和一个正整数m

第二行:一个只含有0和1的长度为n的字符串,表示编号为1到n的灯的状态

接下来m行,每行有1个数o或者3个数o,a,b,如果o是0,代表数一下有多少个关着的灯;如果o是1,代表数一下有多少个开着的灯;如果o是2,代表将编号为a到b的灯(含a和b)进行取反操作;如果o是3,代表将编号为a到b的灯(含a和b)进行开灯操作;如果o是4,代表将编号为a到b的灯(含a和b)进行关灯操作。

输出

对于数灯的操作结果,各输出一行。

样例输入

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

样例输出

3
4

提示

第一个操作:数开着的灯,共3个(3,4,5),输出3;

第二个操作:将第2-3之间的灯全部取反,得到01011

第三个操作:将第1-1之间的灯全部开灯,得到11011

第四个操作:将第4-5之间的灯全部关灯,得到10000

第五个操作:数关着的灯,共4个(2,3,4,5),输出4。

【数据范围】

50%的数据:n < 32,m < 100000

100%的数据:n < 64,m <= 1000000

标签

[上一题][提交][讨论版][状态][下一题]