分数: 600 点
问题陈述
给你一个序列 A=(A_1,\ldots,A_N) 长度 N。 每个元素是 0, 1,或 2.
流程 Q 按顺序查询。 每个查询属于以下类型之一:
1 L R:打印序列的反转数 (A_L,\ldots,A_R).2 L R S T U:对于每个 i 这样 L\leq i \leq R,如果 A_i is 0,替换为 S;如果 A_i is 1,替换为 T;如果 A_i is 2,替换为 U.
反转数是多少?
序列的反转数 B = (B_1, \ldots, B_M) 是整数对的数量 (i, j) (1 \leq i < j \leq M) 这样 B_i > B_j.约束
- 1 \leq N \leq 10^5
- 0 \leq A_i \leq 2
- 1\leq Q\leq 10^5
- 在每个查询中, 1\leq L \leq R \leq N.
- 在第二类的每个查询中, 0\leq S,T,U \leq 2.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \ldots A_N \rm Query_1 \rm Query_2 \vdots \rm Query_Q
\rm Query_i 表示 i-th 查询,采用以下格式之一:
1 L R
2 L R S T U
输出
按给定顺序打印对第一类查询的响应,以换行符分隔。
示例输入 1
5 3 2 0 2 1 0 1 2 5 2 2 4 2 1 0 1 2 5
示例输出 1
3 4
最初, A=(2,0,2,1,0).
- 在 1-st查询,打印反转数 3 of (A_2,A_3,A_4,A_5)=(0,2,1,0).
- 的 2-nd 查询使得 A=(2,2,0,1,0).
- 在 3-rd查询,打印反转数 4 of (A_2,A_3,A_4,A_5)=(2,0,1,0).
示例输入 2
3 3 0 1 2 1 1 1 2 1 3 0 0 0 1 1 3
示例输出 2
0 0