UOJ Logo Universal Online Judge

UOJ

附件下载 统计

小青鱼走在重(zhòng)庆市的街上,突然人群中钻出一个火星人,他要求重庆市选出一支队伍参加 UOI。

重庆市有 $n$ 名 OI 选手,他们都是重量级的。第 $i$ 名选手有攻击力 $a_i$,防御力 $b_i$ 和实力 $c_i$,满足 $a_i \ge b_i$,保证任意两名选手防御力不同。

火星人规定的选拔方式,自然和地球人的传统选拔方式不一样。在火星人的要求下,队伍要按如下方式选拔:

  • 首先,确定三个数 $l,r,k$,队伍将从第 $l$ 到第 $r$ 个人中选出 $k$ 个组成。

  • 排在前 $k$ 个的选手为初始的队伍,即第 $l,l+1,\ldots,l+k-1$ 名选手。

  • 接下来,后面的选手按照 $l+k,l+k+1,\ldots,r$ 的顺序依次考虑,对于每名选手 $i$:

    • 若存在一个当前在队伍中的选手 $j$ 满足 $b_j\leq a_i$,则 $i$ 会把 $j$ 放逐,使得 $j$ 退出队伍,$i$ 进入队伍。若有多个符合条件的 $j$,则 $b_j$ 最小者会被放逐。

    • 否则,$i$ 会放逐自己,什么也不会发生。

  • 所有人考虑完后,就得到了最终的队伍成员名单。

选拔一共进行了 $q$ 轮,每轮给定不同的 $l,r,k$,求按照上述规则选 $k$ 名选手组成队伍,队伍成员的实力 $c_i$ 之和。

输入格式

第一行:两个整数 $n,q$。

第二行:$n$ 个整数 $a_1,\ldots,a_n$。

第三行:$n$ 个整数 $b_1,\ldots,b_n$。

第四行:$n$ 个整数 $c_1,\ldots,c_n$。

接下来 $q$ 行:每行三个整数 $l,r,k$。

输出格式

对于每轮选拔,输出一行一个整数表示答案。

样例一

input

5 3
4 4 3 5 5
4 2 3 1 5
1 10 100 1000 10000
1 4 2
2 5 2
1 5 3

output

1001
10100
10101

explanation

第一次询问:最开始 $1,2$ 在队伍,$3$ 放逐了 $2$,然后 $4$ 放逐了 $3$。

第二次询问:最开始 $2,3$ 在队伍,$4$ 放逐了 $2$,然后 $5$ 放逐了 $4$。

第三次询问:最开始 $1,2,3$ 在队伍,$4$ 放逐了 $2$,然后 $5$ 放逐了 $4$。

样例二/三/四

见附件下载,它们分别对应子任务 1,3,5

数据范围

对于全部数据:$1\leq n,q\leq 5\times 10^5,\ 1\leq a_i,b_i\leq n,\ 1\leq c_i\leq 10^9,\ 1\leq l\leq r\leq n,\ 1\leq k\leq r-l+1$,保证任意两名选手防御力不同。

子任务编号 $n\leq$ $q\leq$ 特殊性质 分值
1 $200$ $200$ $10$
2 $2000$ $2000$ $15$
3 $2\times 10^5$ $2\times 10^5$ $k=1$ $25$
4 $25$
5 $5\times 10^5$ $5\times 10^5$ $25$

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$