分数: 100 点
问题陈述
给你一个二进制数组 A=(A_1,A_2,\cdots,A_N) 长度 N.
流程 Q 以下类型的查询。的 i-第一个查询由三个整数表示 T_i,L_i,R_i.
- T_i=1:替换的值 A_j 与 1-A_j 对于每个 L_i \leq j \leq R_i.
- T_i=2: 计算数组的反转(*) A_{L_i},A_{L_i+1},\cdots,A_{R_i}.
注:数组的反转 x_1,x_2,\cdots,x_k 是整数对的个数 i,j 与 1 \leq i < j \leq k, x_i > x_j.
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 1
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq T_i \leq 2
- 1 \leq L_i \leq R_i \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \cdots A_N T_1 L_1 R_1 T_2 L_2 R_2 \vdots T_Q L_Q R_Q
输出
对于每个查询 T_i=2,打印答案。
样本输入 1
5 5 0 1 0 0 1 2 1 5 1 3 4 2 2 5 1 1 3 2 1 2
示例输出 1
2 0 1
- 第一个查询:打印 2,这是 (A_1,A_2,A_3,A_4,A_5)=(0,1,0,0,1).
- 第二个查询:替换 的值 A_3 和 A_4 与 1 和 1。
- 第三个查询:打印 0,这是 (A_2,A_3,A_4,A_5)=(1,1,1,1).
- 第四个查询:替换值 A_1, A_2 和 A_4 与 1, 0 和 0。
- 第五个查询:打印 1,这是 (A_1,A_2)=(1,0).