QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+7]

# 5098. 第一代图灵机

Statistics

题目背景

一天,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

对于所有数据,1mn2×105,q2×105,ci[1,m],0ai109