#P17624. 八云蓝自动机 Ⅱ

八云蓝自动机 Ⅱ

P7709 「Wdsr-2.7」八云蓝自动机 Ⅱ

题目描述

八云蓝自动机维护了一个长度为 nn 的序列 AA ,每个元素都有一个初始值。同时自动机会支持以下三种操作:

  • 1 l r k\colorbox{f0f0f0}{\verb!1 l r k!} :将区间 [l,r][l,r] 内的所有数字全都变为 kk ,即 Al←k,Al+1←k,⋯ ,Ar←kA_l\gets k,A_{l+1}\gets k,\cdots ,A_r\gets k 。

  • 2 x y\colorbox{f0f0f0}{\verb!2 x y!} :交换 AxA_x 与 AyA_y 的值。

  • 3 x\colorbox{f0f0f0}{\verb!3 x!} :查询 AxA_x 的值。

为了测试八云蓝自动机的效率,紫需要进行非常非常多次的测试。为了生成每个测试的所有操作,紫构造出了一个长度为 mm 的操作序列 BB , BB 中的元素就是八云蓝自动机可以执行的一个操作。

设 Υ(l,r)\Upsilon(l,r) 表示从初始状态开始,依次执行 Bl,Bl+1,⋯BrB_l,B_{l+1},\cdots B_r 操作后,所有操作 33 的结果之和。特别地,如果这些操作中没有操作 33 ,那么 Υ(l,r)=0\Upsilon(l,r)=0 。

紫会向八云蓝自动机发起 qq 次询问,每次给出一组 (l,r,p)(l,r,p) ,八云蓝自动机需要计算出

$$\left(\sum_{i=l}^r \Upsilon(i,p)\right) \mod 2^{32}$$

输入格式

  • 第一行两个整数 n,mn,m ,含义如题面所示。

  • 第二行 nn 个整数,表示序列 AA 的初始值。

  • 接下来 mm 行,描述操作序列 BB 。对于每个操作,首先是一个整数 opop 描述操作的种类。

    • 如果 op=1op = 1,接下来三个整数 l,r,kl,r,k ,描述一个操作 11 。

    • 如果 op=2op = 2,接下来两个整数 x,yx,y ,描述一个操作 22 。

    • 如果 op=3op = 3,接下来一个整数 xx ,描述一个操作 33 。

  • 接下来一行,一个整数 qq,表示八云紫发起的询问总数。

  • 接下来 qq 行,每行有三个整数 l,r,pl,r,p,描述一次询问,具体执行方式如题面所示。

输出格式

  • 共 qq 行,每行一个整数,表示此次询问的结果。

输入输出样例 #1

输入 #1

10 10
12 11 6 6 1 18 9 1 13 20 
2 1 8
1 7 7 12
2 4 10
2 5 10
2 9 5
3 7
1 4 8 7
1 1 9 13
3 5
3 6
10
1 4 10
3 3 3
2 2 7
1 4 6
2 2 9
1 8 8
2 6 8
2 6 8
2 5 6
1 4 9

输出 #1

146
0
12
42
25
60
48
48
39
94

说明/提示

  • 本题有且仅有一个 Subtask\textbf{Subtask} 。在本 Subtask\text{Subtask} 中,前几组数据满足 n,m,q≤5×103n,m,q \le 5 \times 10^3,可供检验你的算法的正确性。

  • 对于 100%100\% 的数据,满足:

    • 1≤n,m,q≤3×1051 \le n,m,q \le 3 \times 10 ^ 5。

    • $1 \le a_i,k \le 10^9;1 \le op \le 3;1 \le x,y \le n;x \neq y$。

    • 对于所有操作,1≤l≤r≤n1 \le l \le r \le n;对于所有查询 1≤l≤r≤p≤m1 \le l \le r \le p \le m。