题目类型说明

这是一道提交函数题 / 交互式接口题。

你需要实现题目要求的函数，不需要编写 main，也不能自行从标准输入读取或向标准输出写入。

题目描述

给定一个长度为 N 的序列：

$$a_0, a_1, \dots, a_{N-1}$$

以及一个整数 K。

在这个序列上会发生两类操作：

• 修改（modify）：给定 pos 和 val，表示将 a_{pos} 改为 val；
• 询问（calculate）：定义

$$v(a) = (a_0 \oplus a_1) + (a_1 \oplus a_2) + \cdots + (a_{N-2} \oplus a_{N-1})$$

其中 ⊕ 表示按位异或。对于一次询问，你可以额外临时修改至多 K 个元素，目标是让 v(a) 尽量小，要求返回这个最小可能值。

注意：

• 询问时允许进行的这 K 次修改只用于本次最优值计算；
• 它们不会真正改变原数组；
• 因而也不会影响后续操作。

请编写程序维护上述操作。

你需要实现的函数

void initialize(int N, int K, std::vector<int> a);
void modify(int pos, int val);
long long calculate();

程序执行过程如下：

1. 开始时会恰好调用一次 initialize(N, K, a)；
2. 之后总共会调用 Q_M 次 modify 和 Q_I 次 calculate。

你的程序必须：

• 实现这三个函数；
• 不要包含 main；
• 不要读写标准输入输出；
• 包含头文件：

#include "minimize.h"

除此之外，你可以自由定义辅助函数、变量、常量等。

本地测试格式

题目提供 minimize.h 和 Lgrader.cpp，可与你的程序一起编译本地测试。

本地 grader 的标准输入格式如下：

• 第 1 行：N K
• 第 2 行：a_0, a_1, ..., a_{N-1}
• 第 3 行：Q
• 接下来 Q 行，每行是一条操作，格式为以下两种之一：
  • 0：表示一次询问；
  • 1 pos val：表示一次修改。

其中：

$$Q = Q_M + Q_I$$

数据范围

• 1 ≤ N ≤ 100000
• 1 ≤ K ≤ 20
• K ≤ N
• 1 ≤ Q_I ≤ 1000
• 0 ≤ Q_M ≤ 50000
• 0 ≤ a_i < 2^{31}

子任务与评分

子任务	N	额外限制	分值
1	≤ 15	无	5
2	≤ 1000	Q_I ≤ 1，Q_M = 0
3	≤ 100000		10
4	≤ 1000	无
5	≤ 100000	Q_M ≤ 1000	30
6		K = 1	2
7		K ≤ 2
8		K ≤ 10	6
9		无	30

样例交互

Grader                     Your program
initialize(5, 2, [1, 9, 4, 6, 2])    -
calculate() returns 6                
modify(1, 3)                         -
modify(2, 3)                         -
calculate() returns 1                

样例解释

初始时：

N = 5, K = 2, a = [1, 9, 4, 6, 2]

对于第一次询问，我们可以把前两个值改成 4，得到：

[4, 4, 4, 6, 2]

此时：

$$(4 \oplus 4) + (4 \oplus 4) + (4 \oplus 6) + (6 \oplus 2) = 0 + 0 + 2 + 4 = 6$$

然后执行两次修改后：

• a_1 = 3，此时 a = [1, 3, 4, 6, 2]
• a_2 = 3，此时 a = [1, 3, 3, 6, 2]

对于第二次询问，我们可以把位置 0 和 3 上的值改为 3，得到：

[3, 3, 3, 3, 2]

于是：

$$(3 \oplus 3) + (3 \oplus 3) + (3 \oplus 3) + (3 \oplus 2) = 0 + 0 + 0 + 1 = 1$$