跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#CF276C. Little Girl and Maximum Sum

Little Girl and Maximum Sum

题目描述

给定一个长度为 nn 的数组和 qq 个闭区间询问,每次询问的答案为该区间内所有元素之和。你可以在回答任何询问之前,将整个数组重新排列一次。求所有询问答案之和的最大可能值。排列只做一次,之后所有询问使用同一个数组。

输入格式

第一行输入 n,qn,q。第二行输入 nn 个整数 aia_i。接下来 qq 行,每行输入 li,ril_i,r_i。数组下标从 1 开始。

输出格式

输出一个整数,表示所有询问答案之和的最大值。

数据范围

1≤n,q≤2×1051\le n,q\le2\times10^5;1≤ai≤2×1051\le a_i\le2\times10^5;1≤li≤ri≤n1\le l_i\le r_i\le n。答案可能超过 32 位整数范围。

样例

3 2
1 2 9
1 1
1 2
20

来源

Codeforces 276C。题意按原题整理,保留原题署名;测试数据由本站独立构造。