题目描述
blablabla
样例
5
1 2 3 4 5
2
1 3
2 5
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//使用二维前缀和+差分
#include <iostream>
#include <algorithm>
typedef long long LL;
const int N=100010;
int n,m;
LL a[N]={0};
LL s[N]={0};
using namespace std;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
int l,r;
for(int i=m;i>=1;i--)
{
cin>>l>>r;
s[l]++;
s[r+1]--;
}
for(int i=1;i<=n;i++)
{
s[i]+=s[i-1];
}
LL sum1=0;
for(int i=1;i<=n;i++)
{
sum1+=(a[i]*s[i]);
}
sort(a+1,a+n+1);
sort(s+1,s+n+1);
LL sum=0;
for(int i=1;i<=n;i++)
{
sum+=(a[i]*s[i]);
}
cout<<LL(sum-sum1);
system("pause");
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla