TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5954
  • 题目
  • P5954【序列的欢乐赛】序列排序
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    问题描述

    nodgd在刷题时经常遇到序列排序的问题,于是他自己出了一道:

    对一个长度为$n$的整数序列进行$m$次提问,第$i$次问第$l_i$个数到第$r_i$个数的和是多少。在所有提问开始前,nodgd要求你对这个序列重新排序,使$m$次提问的答案总和尽量大。你需要把答案总和的最大值汇报给nodgd。

    输入格式

    第一行一个整数$n$。第二行$n$个整数$a_1,a_2,\dots,a_n$。

    第三行一个整数$m$。接下来$m$行中的第$i$行有两个整数$l_i,r_i$,表示一次提问。

    输出格式

    输出一个整数,表示重新排序后$m$次提问的答案总和的最大值。

    样例输入 1

    3
    1 2 3
    3
    1 2
    2 3
    3 3

    样例输出 1

    11

    样例输入 2

    5
    123456 234567 345678 456789 567890
    5
    1 2
    2 3
    3 4
    4 5
    1 5

    样例输出 2

    4827117

    提示

    样例说明1
    如果不进行重新排序,三次提问的答案分别为3,5,3,总和是11。而且,无论如何排序,答案总和都不会超过11。

    数据规模与约定
    对于30%的数据,\(n,m\le200\)
    对于60%的数据,\(n,m\le2000\)
    对于100%的数据,\(n,m\le200000\),$1\le a_i\le10^6$,$1\le l_i\le r_i\le n$。


    来源  感谢nodgd