私はこの問題を解決しようとしています:
少女には n 個の要素の配列があります (配列の要素には 1 から始まるインデックスが付けられます)。
また、"q" 個のクエリがあり、それぞれが一対の整数li, ri (1 ≤ li ≤ ri ≤ n)によって定義されます。クエリごとに、li から ri までのインデックスを持つ配列の要素の合計を見つける必要があります。
少女はその問題がかなりつまらないことに気づきました。彼女は、クエリ応答の合計が可能な限り最大になるように、クエリに応答する前に配列要素を並べ替えることにしました。あなたの仕事は、この最大合計の値を見つけることです。
入力：
最初の行には、スペースで区切られた 2 つの整数 n (1 ≤ n ≤ 10^5) と q (1 ≤ q ≤ 10^5) が含まれています。これは、配列内の要素の数とクエリの数です。
次の行には、スペースで区切られた n 個の整数 ai (1 ≤ ai ≤ 10^5) — 配列要素が含まれます。
次の q 行のそれぞれには、スペースで区切られた 2 つの整数li と ri (1 ≤ li ≤ ri ≤ n) — i 番目のクエリが含まれます。
出力：
1 行に 1 つの整数 (配列要素が並べ替えられた後のクエリ応答の最大合計) を出力します。
Sample testcases:
input:
3 3
5 3 2
1 2
2 3
1 3
output
25
input
5 3
5 2 4 1 3
1 5
2 3
2 3
output
33
私はセグメント ツリーの知識を持っているので、セグメント ツリーを介して遅延伝播アプローチを適用しました。
私の努力コード:
#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <list>
#include <cmath>
#include <stack>
using namespace std;
#define scan(x) scanf("%d",&x)
#define print(x) printf("%d ",x)
#define println(x) printf("%d\n",x)
#define For(i,a,j,k) for (i = a; i < j; i+= k)
#define For_back(i,a,j,k) for (i = j; i >= a; i-= k)
#define SET(a,x) memset(a,x,sizeof(a))
#define mod 1000000007
#define inf 0x7fffffff
#define Max 2000000
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
long long int tree[3*Max];
long long int lazy[3*Max];
void update(int node,int a,int b,int i,int j,long long int value)
{
if (lazy[node]!= 0)
{
tree[node] += lazy[node];
if (a != b)
{
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (a > b || a > j || b < i)
return;
if (a >= i && b <= j)
{
tree[node] += value;
if (a != b)
{
lazy[2*node] += value;
lazy[2*node+1] += value;
}
return;
}
int mid = (a+b)/2;
update(2*node,a,mid,i,j,value);
update(2*node+1,mid+1,b,i,j,value);
tree[node] = (tree[2*node]+tree[2*node+1]);
}
long long int query(int node,int a,int b,int i,int j)
{
if (a> b || a > j || b < i) return 0;
if (lazy[node] != 0)
{
tree[node] += lazy[node];
if (a != b)
{
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (a >= i && b <= j)
return tree[node];
int mid = (a+b)/2;
long long int q1 = query(2*node,a,mid,i,j);
long long int q2 = query(2*node+1,mid+1,b,i,j);
return ((q1+q2));
}
int main()
{
SET(lazy,0);
SET(tree,0);
int n,m;
cin >> n >> m;
int i,j;
int arr[n];
For(i,0,n,1)
{
cin >> arr[i];
}
sort(arr,arr+n);
For(i,0,m,1)
{
long long int num1,num2;
cin >> num1 >> num2;
update(1,0,n-1,num1-1,num2-1,1);
}
long long int my[n];
For(i,0,n,1)
{
long long int number = query(1,0,n-1,i,i);
my[i] = number;
}
sort(my,my+n);
long long int sum = 0;
For_back(i,0,n-1,1){
sum += my[i]*arr[i];
}
cout << sum << endl;
return 0;
}
これに対する私のアプローチは、セグメントツリーを使用して前述のように実行し、最後に答えを出力するだけの簡単なものでした。
私の質問は、これのためのより単純なアルゴリズムはありますか? または、セグメント ツリー コードを最適化する必要がありますか?