#P8543. 「Wdoi-2」纯粹的复仇女神
「Wdoi-2」纯粹的复仇女神
题目背景
「因为,人类的历史与成长,就是战争的历史与成长。没有纷争,就没有成长。满足于现状,就等于人类放弃了生存。月之民每天都为地上人考虑着。地上人的历史,就是月之民创造的。」
「我对月之民还是很了解的。这么说吧,她们在各式各样的异世界的居民中,属于最恶劣的那一类。超级排他,超级没自由,虚构的乐园,虽然擅长鄙视别人,但无法容忍自己被当成笨蛋。她们甚至认为其他世界的居民连杂菌都不如。」
「最重要的问题是,月之民敌视着幻想乡,就是这样的。」
「没想到竟然会把地上人送到月面上来,之前丝毫没有过这种想法呢。那些眼里容不下一点沙子的月之民,竟然会使用这种不入流的手段。」
「幻想乡被作为人质绑架了,可以这么认为吧?要是想拯救幻想乡的话,就不许对月之都动手,就是这种不人道的策略。」
遥遥 万公里航程之外,于此故乡之星倒映之海,打败不共戴天之敌,击碎永久不得醒之梦。
不倶戴天の敵、よ。見てるか!?
不共戴天之敌,嫦娥啊。你在看着吗!?
题目描述
简要题意
给定一个长度为 的序列,序列中每个元素是一个二元组 ,分别表示颜色与权值。
现在有 次询问,每次给出一个区间 ,求:
特别地,如果 内没有颜色为 的值,后面的部分定义为 。
原始题意
纯狐的能力是纯化,一旦灵梦身上的污秽被纯化,则必死无疑。
灵梦携带了 张一字排开的灵符用于转嫁污秽,但纯狐依旧可以纯化附着在上面的污秽,置灵梦于死地。
具体地,每次纯狐命中一个区间 中的所有灵符,灵梦需要在此之前净化这些灵符上面的污秽。
每张灵符有固定的颜色 ,经过激烈的战斗,每张灵符上沾染了 单位的污秽。
同种颜色的灵符之间相互作用,净化区间内一批相同颜色的灵符,其灵力花费为这些灵符上污秽的最小值。
由于逸散的灵力可以为其他灵符所吸收,灵梦只需知道该区间内所有颜色的灵符净化花费的最大值,此为她净化一次的灵力花费。
给定 和 ,每次给出纯狐的一种可能的攻击 ,问灵梦净化一次的灵力花费。注意只是计算,每次给出答案后并不改变 和 。
输入格式
第一行两个整数 ,表示序列长度与询问次数。
第二行 个整数,依次为 。
第三行 个整数,依次为 。
接下来 行,每行两个整数 ,表示每次询问给出的区间。
输出格式
共 行,每行一个整数,表示本次询问的答案。
提示
样例 1 解释
如图,数字代表权值,背景色代表颜色。
- 对于区间 ,出现的两种颜色对应的权值最小值为 和 ,取最大值答案为 。
- 对于区间 ,出现的三种颜色对应的权值最小值为 和 ,取最大值答案为 。
- 对于区间 ,出现的三种颜色对应的权值最小值为 和 ,取最大值答案为 。
- 对于区间 ,出现的两种颜色对应的权值最小值为 和 ,取最大值答案为 。
- 对于区间 ,出现的一种颜色对应的权值最小值为 。 其余同理。
数据范围及约定
特殊性质 :所有的 。
对于全部数据,保证 ,,,。