晶块链表¶
- 参考时间限制：0.5 秒（评测环境与性能）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
背景故事¶
DNF 的活动中，玩家们共同操作一列晶块。把一段晶块换成指定种类时，每个位置都会按照新旧能量的差值贡献分数。活动还允许调整某一种晶块的能量，因此同一次替换在不同时间可能得到不同分数。
形式化问题描述¶
有 \(n\) 个位置，编号为 \(1,\ldots,n\) ，共有 \(k\) 种晶块，种类编号为 \(1,\ldots,k\) .位置 \(i\) 当前的种类为 \(c_i\) ，种类 \(t\) 当前的能量为 \(e_t\) .
依次执行 \(m\) 次操作：
0 l r c：先按操作前的状态计算分数
输出该分数，再把区间 \([l,r]\) 内所有位置的种类设为 \(c\) .
- 1 c e ：把种类 \(c\) 的能量设为 \(e\) .这会影响所有该种类晶块在后续计分时的能量，但不改变任何位置的种类，也不产生分数。
不同种类可以具有相同能量。即使某次替换的分数为零，种类修改仍然生效。
输入格式¶
第一行三个整数 \(n,k,m\) .第二行 \(n\) 个整数，为初始种类 \(c_1,\ldots,c_n\) .第三行 \(k\) 个整数，为初始能量 \(e_1,\ldots,e_k\) .
接下来 \(m\) 行，每行一个操作。第二行或第三行对应的数量为零时，该行为空行。
输出格式¶
对每个操作 0，按出现顺序输出一行整数。没有此类操作时不输出任何内容。
样例 1¶
输入¶
5 5 5
1 2 3 4 5
1 2 3 4 5
0 1 2 3
0 1 2 1
1 4 1
0 1 5 5
0 5 5 4
输出¶
3
4
14
4
样例 2¶
输入¶
3 2 4
1 1 2
5 5
0 1 3 1
1 1 2
0 1 3 2
0 2 2 2
输出¶
0
9
0
样例 3¶
输入¶
0 0 0
输出¶
样例解释¶
样例 1 首次替换得到 \(|1-3|+|2-3|=3\) .修改第四种晶块的能量后，最后两次替换按更新后的能量计分。
样例 2 的第一次替换得分为 \(0\) ，但三个位置都变成了种类 \(1\) .将其能量改为 \(2\) 后，再全部替换为能量 \(5\) 的种类 \(2\) ，得分为 \(9\) .样例 3 为空实例，输出为空。
数据范围与保证¶
对 100% 的数据：\(0\le n,k\le500000\) ，\(0\le m\le100000\) .每个出现的种类编号均在 \(1,\ldots,k\) 内，初始和修改后的能量均满足 \(1\le e\le50000\) .
每次操作 0 满足 \(1\le l\le r\le n\) .所有输入合法：例如 \(n>0\) 时必有 \(k>0\) ，\(n=0\) 时没有操作 0，\(k=0\) 时没有任何操作。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |