题目背景
一天,wind_whisper 遇到了一道题:“第二代图灵机”。
经过长时间的坐牢之后,他终于有了一个屎山做法。然而,这个做法虽然麻烦,但似乎可以不依赖随机数据?
但是由于 wind_whisper 码力太差,他发现自己根本写不出来...
于是他把操作进行了弱化,出成了这道简单题。
既然是弱化,不妨就叫它“第一代图灵机”吧。
题目描述
给出一个长度为 n 的非负数字序列 a1...n,每个数字有一个 [1,m] 的颜色 ci,要求进行 q 次操作,操作分为两类:
1 l r
:询问区间 [l,r] 中没有重复颜色且数字和最大的子区间的数字和。2 i w
:把 ci 修改为 w。
输入格式
第一行三个正整数 n,m,q。
第二行 n 个整数,表示 a1...n。
第三行 n 个整数,表示 c1...n。
接下来的 q 行,每行表示一次操作,格式如题目描述。
输出格式
对于每个第一类操作输出一行一个整数,表示答案。
样例数据
样例 1 输入
3 3 3
1 1 2
1 1 2
1 1 3
2 2 2
1 1 3
样例 1 输出
3
2
样例2 ~ 4
见下发文件。
数据范围
子任务编号 | n≤ | q≤ | m≤ | 特殊性质 | 分值 |
---|---|---|---|---|---|
1 | 5000 | 5000 | n | 无 | 10 |
2 | 2×105 | 2×105 | 10 | 10 | |
3 | n | 没有第二种操作 | 20 | ||
4 | 5×104 | 5×104 | 无 | 20 | |
5 | 2×105 | 2×105 | 40 |
对于所有数据,1≤m≤n≤2×105,q≤2×105,ci∈[1,m],0≤ai≤109。