UOJ Logo Universal Online Judge

UOJ

#784. 新年的传火仪式

附件下载 统计

你对着面前清一色的 TLE 出了神,你发现你的时限竟然配错了,无奈你剩下能区分的手段已经不多了。

正巧,一年一度的粉兔传火大会就要开始了,粉兔们会依次排成一行进行传火的仪式。

传说传过火炬的粉兔在新的一年都会获得好运,但有的时候有的粉兔会因为各种急事离开座位。

粉免很有可能会在传火大会上进行各种破坏活动。所以在仪式开始之前,你需要对可能发生的紧急情况做一个预演。由于时间是连续的,因此你只需要考察一段连续的区间内可能会发生的紧急情况。

在仪式开始前,并不是所有的粉兔都已经就位。具体来说,有 $n$ 只粉兔排成一行,从左到右依次坐在第 $1\sim n$ 个位置。初始时有一个序列 $a$,只有 $a_i=1$ 的位置 $i$ 上的粉兔已经就座。在这之后会按照预演计划,依次发生 $m$ 个事件。每个事件都形如以下四种之一:

  1. 0 p 表示第 $p$ 个位置上的粉兔离开了座位。如果这个位置本来就没有粉兔,那么这个事件发生之后这个位置上仍然没有粉兔。
  2. 1 p 表示第 $p$ 个位置上有一只粉兔就座了。如果这个位置本来就有粉兔,那么这个事件发生之后这个位置上仍然有粉兔。
  3. ! p 表示第 $p$ 个位置上粉兔的就座情况发生了改变:如果这个位置上先前没有粉兔,就会有一只粉兔在此就座;如果这里本来有一只粉兔,在这之后这个位置上就没有粉兔了。
  4. > 兔王高呼“传火”,这个时候如果火炬所在的位置有粉兔,则这一事件之后火炬所处的位置变为当前位置的下一个位置,否则火炬不动。当然下一个位置有可能不存在,此时称这个位置为第 $n+1$ 个位置。

初始时火炬在第 $1$ 个位置上。经过一系列事件以及传火的尝试后,火炬最后会处在某一个位置上。

由于需要预演紧急情况,兔王提出了 $q$ 个问题,其中每个问题形如 $l,r$,表示如果第 $l$ 到第 $r$ 个事件依次发生(且仅发生这些事件),火炬最后应该在哪个位置上。你需要依次回答这 $q$ 个问题。当然由于这是排练,因此每一次预演之间都是互不影响的。

输入格式

第一行一个字符 $\text{A}$ 或者 $\text{B}$ 表示数据类型。在本题中,你需要针对两种不同的情况分别设计算法。

第二行三个整数 $n,m,q$ 与题目对应,分别表示粉兔的个数,事件的个数和询问的个数。

第三行一个 $01$ 串,表示初始的就座情况:第 $i$ 个位置为 $1$ 表示第 $i$ 个位置上初始有粉兔,否则表示没有。

接下来 $m$ 行每行一个操作,形如以下四种格式之一:

  • 0 p 表示第 $p$ 个位置上的粉兔离开座位;
  • 1 p 表示第 $p$ 个位置上的粉兔回到座位;
  • ! p 表示第 $p$ 个位置上的粉兔就座状态发生改变;
  • > 表示一次传火的尝试。

再接下来 $q$ 行,每行两个整数 $l,r$,表示对 $[l,r]$ 中的事件进行预演。

输出格式

共 $q$ 行每行一个整数,表示每次预演最后火炬传递到了哪个位置。

样例一

input

A
2 5 5
00
1 1
>
>
1 2
>
1 1
1 2
1 3
1 4
1 5

output

1
2
2
2
3

样例二

input

B
4 20 20
1011
>
0 1
>
1 1
>
1 3
>
0 2
! 2
>
>
>
! 3
0 4
0 4
>
>
1 3
0 1
>
1 10
5 15
2 11
14 15
13 14
11 18
6 18
2 16
10 13
4 5
13 20
15 19
3 11
12 18
13 15
5 8
16 17
16 19
3 20
2 14

output

3
5
4
1
1
2
5
5
2
2
2
2
4
2
1
2
2
2
5
5

样例三

见附件下载。该样例满足子任务 1,3 的限制。

样例四

见附件下载。该样例满足子任务 2,3 的限制。

样例五

见附件下载。该样例满足子任务 3 的限制。

样例六

见附件下载。该样例满足子任务 4,5 的限制。

样例七

见附件下载。该样例满足子任务 5 的限制。

数据范围与提示

本题有两种数据类型:$\text{A}$ 和 $\text{B}$。

子任务 $1,2,3$ 属于数据类型 $\text{A}$。对于属于类型 $\text{A}$ 的所有数据,保证 $1\leq n\leq2\times10^5$,$1\leq m,q\leq10^6$。所有 $a_i$ 均为 $0$。不存在 ! 操作。以下是子任务 $1,2,3$ 的具体情况及特殊性质:

子任务编号 $n\leq$ 特殊性质 分值 子任务依赖
$1$ $100$ / $10$ /
$2$ $2\times10^5$ 不存在 0 操作 $20$ /
$3$ $2\times10^5$ / $20$ $1,2$

子任务 $4,5$ 属于数据类型 $\text{B}$。对于属于类型 $\text{B}$ 的所有数据,保证 $1\leq n,m,q\leq2\times10^5$。以下是子任务 $4,5$ 的具体情况及特殊性质:

子任务编号 特殊性质 分值 子任务依赖
$4$ 不存在 ! 操作 $20$ /
$5$ / $30$ $4$

对于所有数据,$a_i\in\{0,1\}$,$\text{op}_i\in\{$0$,$1$,$!$,$>$\}$,$1\leq p\leq n$,$1\leq l\leq r\leq m$。

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$