← 返回题目列表

AtCoder · abc265_g

G. 012 反转

中文机器翻译题面 查看原题

分数: 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