#2941. 01序列

01序列

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有一个 nn 位的二进制数。

我们将对其进行 qq 次操作。每次操作,我们都会是以下三种操作之一:

1 i j1\ i \ j:将这个数与上 (2n1)(2i2j)(2^n-1)⊕(2^i-2^j)(保证 i>ji>j)。

2 i j2\ i\ j:将这个数或上 2i2j2^i-2^j(保证 i>ji>j)。

3 i j3\ i\ j:求从低往高第 ii 位到第 jj 位之间,每一位都相等的区间的最长长度(保证 iji≤j)。

输入格式

第一行两个正整数 n,qn,q

第二行一个长度为 nn0101 串,表示这个二进制数。

接下来 qq 行,每行三个整数,表示一次询问。

输出格式

对于每个 33 操作,输出一行一个整数表示最长相等区间的长度。

输入样例 1

8 5
10010111
3 3 7
1 3 1
3 1 5
2 7 3
3 3 8

输出样例 1

2
3
5

样例解释

11操作后,这个数变成了10010001。

22操作后,这个数变成了11111001。

数据范围

下表数据表示数据最大值。

Subtask n q 特殊性质 分值
1 63 10
2 5000
3 10^5 不含操作1 15
4 不含操作2
5 50

第二届小云雀杯提高组

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-4-23 19:30
结束于
2023-4-23 22:18
持续时间
2.8 小时
主持人
参赛人数
210