← 返回题目列表

AtCoder · practice2_l

L. 惰性线段树

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

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