Substring

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

Description

你有一个字符串 s=S1S2…Sns = S_1 S_2 \dots S_n,其中每个字符是 0 或 1。你需要处理 qq 条命令,每条命令是以下两种类型之一:

  1. 1 l r:将区间 [l,r][l, r] 内的每个字符设置为 0。
  2. 2 l r:将区间 [l,r][l, r] 内的每个字符设置为 1。
  3. 3 l r:翻转 ss 的区间 [l,r][l, r] 内的每个字符(0 变为 1,1 变为 0)。
  4. 4 l r:求子串 [l,r][l, r] 中互不相同的非空子序列数量,对 1 000 000 0071\,000\,000\,007 取模。

你需要处理所有命令,并对每个类型 4 的命令输出结果。

Constraints and Subtasks

对于所有测试数据,满足:

  • 1≤n,q≤1051 \leq n, q \leq 10^5;
  • SS 的长度为 nn,且仅由 0 和 1 构成;
  • 1≤l≤r≤n1 \leq l \leq r \leq n;
  • 除字符串以外的输入为整数。

另外,还有一些测试点满足特殊要求。

分值 idid n,q≤n,q\leq 特殊性质
20%20\% 11 1010
14%14\% 22 50005000
15%15\% 33 10510^5 不存在操作 1、2、3
1%1\% 44 不存在操作 4
15%15\% 55 不存在操作 3
15%15\% 66 不存在操作 1、2
20%20\% 77

Input

输入格式如下:

$ \boxed{ \begin{aligned} & id \\ & n \quad q \\ & s \\ & t_1 \quad l_1 \quad r_1 \\ & t_2 \quad l_2 \quad r_2 \\ & \vdots \\ & t_q \quad l_q \quad r_q \\ \end{aligned} } $

其中 tit_i 表示第 ii 次操作的操作类型。

Output

对于每个类型 4 的命令,输出一行一个整数,表示区间内互不相同的子序列数量对 1 000 000 0071\,000\,000\,007 取模的结果。

Samples

6 5
110101
4 1 3
1 1 3
2 1 2
3 1 4
4 2 6
5
15

第一个操作要查询 S=S=110 中互不相同的非空子序列数量。

  • 子序列 S1S_1 为 1;
  • 子序列 S2S_2 为 1;
  • 子序列 S3S_3 为 0;
  • 子序列 S1,S2S_1, S_2 为 11;
  • 子序列 S1,S3S_1, S_3 为 10;
  • 子序列 S2,S3S_2, S_3 为 10;
  • 子序列 S1,S2,S3S_1, S_2, S_3 为 110;

互不相同的非空子序列有 1、0、11、10 和 110,所以答案为 55。

海西省理论职专校队选拔赛

未参加
状态
已结束
规则
IOI
题目
23
开始于
2025-4-8 8:30
结束于
2025-5-8 8:30
持续时间
720 小时
主持人
参赛人数
23