← 返回题目列表

Codeforces · 2201/D

D. 二进制非搜索和查询

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

对于由 $$$m$$$ 整数组成的序列 $$$b$$$,集合 $$$S(b)$$$ 被定义为满足以下条件的元组 $$$(i,j,k)$$$ 的集合:

  • $$$i$$$、$$$j$$$、$$$k$$$ 是整数;
  • $$$1 \le k \lt m$$$;
  • $$$1 \le i \lt j \le m-k+1$$$;
  • 对于 $$$b$$$ 中的每个元素 $$$v$$$,$$$v$$$ 在 $$$[b_i,b_{i+1},\ldots,b_{i+k-1}]$$$ 和 $$$[b_j,b_{j+1},\ldots,b_{j+k-1}]$$$ 中出现的次数相同。

例如,当 $$$b=[1,2,1,2]$$$ 时,元组 $$$(1,3,2)$$$ 是 $$$S(b)$$$ 的元素,因为 $$$1$$$ 和 $$$2$$$ 在 $$$[b_1,b_2]$$$ 和 $$$[b_3,b_4]$$$ 中都出现一次。

此外,我们在正整数序列上定义了两个函数:

  • $$$k_\max(b)$$$ 定义为 $$$S(b)$$$ 的所有元素 $$$(i,j,k)$$$ 上 $$$k$$$ 的最大值;
  • $$$f(b)$$$ 定义为 $$$S(b)$$$ 的不同元素 $$$(i,j,k)$$$ 的数量,使得 $$$k=k_\max(b)$$$。

异常,当 集合 $$$S(b)$$$ 为空,它们被定义为 $$$k_\max(b)=0$$$ 和 $$$f(b)=0$$$。

给定一个由 $$$n$$$ 整数组成的序列 $$$a$$$。请回答以下类型的 $$$q$$$ 询问:

  • $$$i\;x$$$:将 $$$a_i$$$ 的值更改为 $$$x$$$。然后,找到 $$$k_\max(a)$$$ 和 $$$f(a)$$$ 的值。

请注意,更新是持久的。换句话说,一个查询的更新也会影响后面的查询。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 100\,000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$)。

以下 $$$q$$$ 行中的每一行都包含两个整数 $$$i_j$$$ 和 $$$x_j$$$ 表示第 $$$j$$$ 查询 ($$$1 \le i_j,x_j \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$100\,000$$$。

输出

对于每个测试用例,输出 $$$q$$$ 行。

在第 $$$j$$$ 行,您必须为第 $$$j$$$ 查询输出 $$$k_\max(a)$$$ 和 $$$f(a)$$$ 的值。

可以证明,在该问题的约束下,两个值都不会超过 $$$10^{11}$$$。

示例

输入
复制

4
5 3
1 2 3 4 5
3 2
4 1
5 2
4 3
1 2 1 1
4 2
3 2
2 1
5 2
1 3 2 4 5
5 3
5 5
8 3
1 2 3 4 1 2 5 4
7 3
7 4
2 1

输出
复制

1 1
3 1
3 3
2 3
2 1
1 2
3 1
0 0
4 10
4 4
4 2

注意

紧接着第二个测试用例的第一个查询之后,$$$a=[1,2,1,2]$$$。集合$$$S(a)$$$的元素如下:

  • $$$(1,3,1)$$$: $$$[\color{红色}{1},2,\color{蓝色}{1},2]$$$;
  • $$$(2,4,1)$$$: $$$[1,\color{红色}{2},1,\color{蓝色}{2}]$$$;
  • $$$(1,2,2)$$$: $$$[\color{红色}{1},\color{洋红色}{2},\color{蓝色}{1},2]$$$;
  • $$$(1,3,2)$$$: $$$[\颜色{红色}{1},\颜色{红色}{2},\颜色{蓝色}{1},\颜色{蓝色}{2}]$$$;
  • $$$(2,3,2)$$$: $$$[1,\color{红色}{2},\color{洋红色}{1},\color{蓝色}{2}]$$$。

因此,$$$k_\max(a)=2$$$,并且$$$f(a)=3$$$,因为存在三个元素$$$(i,j,k)$$$,其中$$$k=k_\max(a)=2$$$。

紧接着第三个测试用例的第二个查询,$$$a=[1,3,2,4,5]$$$。此时集合 $$$S(a)$$$ 为空。

根据定义,您应该输出 $$$k_\max(a)=0$$$ 和 $$$f(a)=0$$$,因为 $$$S(a)$$$ 当前为空。