1512: 时间复杂度优化练习

[命题人 : 2311026]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交解决: 2提交量: 3统计

题目描述  复制

在 O(nm)\mathcal{O}(nm) 的复杂度下求 ∑i=1n∑j=1mmin⁡(ai,bj)\sum\limits_{i=1}^n\sum\limits_{j=1}^m \min(a_i,b_j) 是显然的，那么是否存在一种  O(n+m+V)\mathcal{O}(n+m+V) 的算法可以解决呢？（其中 VV 为值域）

输入

第一行为两个正整数 n,mn,m。   
第二行为 nn 个正整数，表示 {an}\{a_n\}。  
第三行为 mm 个正整数，表示 {bm}\{b_m\}。  

输出

共一行一个正整数，为所求答案对 109+710^9+7 取模的结果。

样例输入  复制 

3 3
2 2 3
2 3 2

样例输出  复制 

19

提示

1⩽n,m⩽1051\leqslant n,m\leqslant 10^5，{an}\{a_n\} 和 {bm}\{b_m\} 最大值不超过 10510^5。    
本题不涉及任何高级算法。

必须/禁用关键字

无

来源/分类

MKOI 桶排序 
提交