#P12873. Message Spreading

    ID: 12059 传统题 5000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-交换论证枚举较小维度向下取整与向上取整有序集合区间合并增量维护势能分析2025“钉耙编程”中国大学生算法设计暑期联赛(10)

Message Spreading

Message Spreading

Problem Description

一个星球上有 nn 个国家,编号为 1∼n1\sim n。 对于每个 1≤i<n1\le i< n,第 ii 号国家与第 i+1i+1 号国家互为盟友。特别的,第 11 号国家和第 nn 号国家也互为盟友。 现在有一条消息需要在星球上进行传播。初始时有一些国家知道该消息,有一些国家不知道。 你作为星球的统领者,每天可以进行如下两种传播操作之一:

  • 指定一个国家,告诉该国家消息。该操作会让被指定的一个国家知道该消息。
  • 让所有已经知道该消息的国家告知他们的所有盟友。该操作会使当前至少有一个“已知消息盟友”的国家知道该消息。 你想知道至少需要多少天才能让所有国家都知道该消息。 接下来还有 qq 次修改操作,每次给定 op,l,rop,l,r,表示进行如下修改:
  • 若 op=1op=1,则将编号为 l∼rl\sim r 的所有国家都设置为初始时知道该消息。
  • 若 op=2op=2,则将编号为 l∼rl\sim r 的所有国家都设置为初始时不知道该消息。 每次操作之后,你都需要求出至少需要多少天才能让所有国家都知道该消息。注意,你并不会真正进行传播操作。

Input

本题有多组数据。第一行一个正整数 TT(1≤T≤51\le T\le 5)表示数据组数。对于每组测试数据: 第一行输入两个整数 n,qn,q(1≤n,q≤2⋅1051\le n,q\le 2\cdot 10^5),表示国家数量和修改次数。 第二行输入一个长度为 nn 的只包含字符 0 和 1 的字符串 ss,若 ss 的第 ii 个字符是 0,则表示第 ii 个国家最初不知道该消息,否则表示第 ii 个国家最初知道该消息。 接下来 qq 行,每行三个整数 op,l,rop,l,r(1≤op≤21\le op\le 2,1≤l≤r≤n1\le l\le r\le n),表示一次修改操作。 保证 ∑n,∑q≤5⋅105\sum n,\sum q\le 5\cdot 10^5。

Output

对于每组测试数据,输出 qq 行,每行一个整数,表示每一次修改之后的答案。

Sample Input

1
6 5
011100
1 1 4
2 2 5
1 1 3
1 6 6
2 2 4

Sample Output

1
2
2
1
2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(10)