P5673 「SWTR-2」Picking Gifts
题目背景
$\mathrm{Sunny}$ 有个 $npy$ 叫做小 $\mathrm{b}$。
小 $\mathrm{b}$ 的生日就要到了,$\mathrm{Sunny}$ 想给她买一些礼物。
题目描述
商店里摆着琳琅满目的商品,每个商品都有:
- 编号,**从左到右**依次为 $1,2,\dots n$。
- 种类,分别为 $p_1,p_2,\dots p_n$。
- 价值,分别为 $v_1,v_2,\dots v_n$。
$\mathrm{Sunny}$ 想从中挑选一个区间,将这个区间里的所有礼物买下来送给小 $\mathrm{b}$。
小 $\mathrm{b}$ 会**从右往左**依次查看 $\mathrm{Sunny}$ 送给他的礼物,如果她看到同一种类的礼物出现了 $k$ 次,那么她就不会再去查看这种礼物(包括第 $k$ 个),当然,这些礼物也就失去了原本的价值。
现在,$\mathrm{Sunny}$ 给你了 $m$ 个区间,想让你求出在小 $\mathrm{b}$ 眼中,这个区间的价值。
具体的价值计算见样例。
输入格式
无
输出格式
无
说明/提示
---
### 样例说明
$[1,1]:7$。
$[1,2]:3+7=10$。
$[1,3]:8+3=11$,因为编号为 $1$ 的礼物种类为 $1$,这是种类 $1$ 出现的第 $k(k=3)$ 次,所以她不会再看这种礼物(包括这个)。
$[1,4]:9+8+3=20$。
$[2,6]:5+6+9+8=28$。
$[3,6]:5+6+9+8=28$。
---
### 数据范围与约定
测试点 $1-4:n\leq 100,m\leq 100$。
测试点 $5-6:n\leq 5000,m\leq 5000$。
测试点 $7-10:n\leq 2\times 10^4,m\leq 10^4$。
测试点 $11-15:n\leq 2\times 10^5,m\leq 2\times 10^5$。
测试点 $16-20:n\leq 10^6,m\leq 5\times 10^5$。
对于测试点 $1,2,7,8,11,12,16,17$,有 $k=n$,其余测试点有 $2\leq k