#P17821. [Ontak2022]AQU

    ID: 16764 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>数据结构字符串字符串哈希CF2600线段树算法基础模拟

[Ontak2022]AQU

题目描述

有 nn 个鱼缸,第 ii 个鱼缸中鱼的大小最初为 fif_i。依次处理 qq 个事件。

投喂操作会作用于闭区间 [L,R][L,R] 中的每一个鱼缸,参数为 kk:

  • 类型 1:将大小 xx 改为 kk。
  • 类型 2:将大小 xx 改为 x+kx+k。
  • 类型 3:将大小 xx 改为 max⁡(x,k)\max(x,k)。

类型 0 是询问:给定两个闭区间 [A1,B1][A_1,B_1]、[A2,B2][A_2,B_2],判断两个区间中鱼的大小所组成的多重集合是否相同。忽略顺序,但每个大小的出现次数必须相同。

输入格式

第一行两个整数 n,qn,q。第二行 nn 个整数 f1,…,fnf_1,\ldots,f_n。

接下来 qq 行,每行格式为以下之一:

0 A1 B1 A2 B2
1 L R k
2 L R k
3 L R k

输出格式

对每个类型 0 的事件输出一行,相同输出 YES,否则输出 NO。

数据范围

1≤n,q≤5000001\le n,q\le500000;1≤fi,k≤1091\le f_i,k\le10^9;所有区间合法且非空。

操作后大小可能超过 10910^9,该上界仅约束初始大小和操作参数。

子任务

子任务 附加限制 分值
1 n,q≤2000 7
2 每次询问的两个区间均为单点 14
3 只有类型1投喂 15
4 只有类型1、2投喂 16
5 n,q≤50000 28
6 无额外限制 20

样例 1

输入:

10 10
1 2 3 1 2 1 2 3 1 2
0 1 2 4 5
1 1 2 10
1 4 5 10
3 1 5 8
3 6 10 8
0 1 5 6 10
1 6 7 10
1 9 10 10
0 1 5 6 10
0 3 3 8 8

输出:

YES
NO
YES
YES