#P14909. [UOI 2025 II Stage] Three Queries

    ID: 14125 传统题 3000ms 512MiB 尝试: 7 已通过: 1 难度: 10 上传者: 标签>CF3100分块数据结构莫队扫描线排序

[UOI 2025 II Stage] Three Queries

题目描述

给定一个长度为 nn 的数组 aa,以及 qq 个询问。另有一个无限长的二进制数组 ww,初始时所有 wi=1w_i=1。

询问共有三种类型:

  1. 1 x:翻转 wxw_x 的值,即从 11 变为 00,或从 00 变为 11。
  2. 2 l r:统计数组 aa 的区间 [l,r][l,r] 中,有多少个不同的数满足 wai=1w_{a_i}=1 且 l≤i≤rl \le i \le r。
  3. 3 x t:将 axa_x 赋值为 tt。

请对每个第二类询问输出答案。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤3⋅1051 \le n,q \le 3 \cdot 10^5),分别表示数组长度和询问数量。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n(1≤ai≤1091 \le a_i \le 10^9),表示数组初始值。

接下来 qq 行,每行首先包含一个整数 typetype(1≤type≤31 \le type \le 3),表示询问类型:

  1. 若 type=1type=1,则该询问还包含一个整数 xx(1≤x≤1091 \le x \le 10^9),表示翻转 wxw_x。
  2. 若 type=2type=2,则该询问还包含两个整数 l,rl,r(1≤l≤r≤n1 \le l \le r \le n),表示询问区间 [l,r][l,r] 中满足条件的不同数的数量。
  3. 若 type=3type=3,则该询问还包含两个整数 x,tx,t(1≤x≤n1 \le x \le n,1≤t≤1091 \le t \le 10^9),表示把 axa_x 改为 tt。

输出格式

对于每个第二类询问,单独输出一行答案。

输入 #1

10 5
3 4 3 4 3 2 3 1 2 1
2 2 5
1 3
2 2 5
3 4 5
2 2 5

输出 #1

2
1
2

评分方式

测试点分组如下:

  1. 88 分:n,q≤103n,q \le 10^3;
  2. 66 分:只有第二类询问,且 n=qn=q,li=1l_i=1,ri=ir_i=i;
  3. 1313 分:只有第二类询问;
  4. 1010 分:只有第一类和第二类询问,且所有 aia_i 两两不同;
  5. 1414 分:只有第一类和第二类询问,且所有 waiw_{a_i} 至多改变一次;
  6. 77 分:只有第一类和第二类询问;
  7. 1414 分:只有第二类和第三类询问;
  8. 88 分:任意时刻都有 ai≤100a_i \le 100;
  9. 1010 分:n,q≤5⋅104n,q \le 5 \cdot 10^4;
  10. 1010 分:无额外限制。