Оптимизация или Новый алгоритм для решения этой проблемы?

Question

Оптимизация или Новый алгоритм для решения этой проблемы?

Я пытаюсь решить эту проблему:

Маленькая девочка имеет массив из n элементов (элементы массива индексируются начиная с 1).

Также есть запросы "q", каждый из которых определяется парой целых чисел li, ri (1 ≤ li ≤ ri ≤ n). Для каждого запроса нужно найти сумму элементов массива с индексами от li до ri включительно.

Маленькая девочка сочла проблему довольно скучной. Она решила изменить порядок элементов массива, прежде чем отвечать на запросы таким образом, чтобы сумма ответов на запросы была максимально возможной. Ваша задача - найти значение этой максимальной суммы.

Входные данные:

Первая строка содержит два целых числа через пробел: n (1 ≤ n ≤ 10^5) и q (1 ≤ q ≤ 10^5) - количество элементов в массиве и количество запросов соответственно.

Следующая строка содержит n разделенных пробелом целых чисел ai (1 ≤ ai ≤ 10^5) - элементы массива.

Каждая из следующих q строк содержит два разделенных пробелом целых числа li и ri (1 ≤ li ≤ ri ≤ n) - i-й запрос.

Выход:

В единственной строке выведите единственное целое число - максимальную сумму ответов на запросы после переупорядочения элементов массива.

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;   
}

Мой подход к этому был прост, просто сделать, как сказано, используя дерево сегментов и, наконец, напечатать ответ.

Мой вопрос: есть ли более простой алгоритм для этого? или я должен оптимизировать мой код дерева сегмента?

0

c++ algorithm data-structures segment-tree

Источник

18 июн '13 в 13:56

3 ответа

Решение

Я думаю, что это будет работать - комментарии приглашены

Создайте массив измерения n с именем count и инициализируйте его равным 0. Просмотрите массив Q

Для каждого запроса - от li до ri увеличить счетчик на 1, т.е. количество элементов li до ri. Сортировка массива. N Сортировка массива подсчета (запомните индекс). Возьмите наибольшее из числа и по соответствующему индексу поместите самый высокий элемент из N Продолжить это для всех элементов

По сути, мы гарантируем, что самый высокий элемент встречается наибольшее количество раз (когда на него ссылается запрос)

1

Источник

user2496562 18 июн '13 в 14:19

Вот что я бы сделал:

Создал (хеш) индекс карты-> кол. Просмотрите все запросы и для каждого индекса в диапазоне увеличьте счетчик (*).
Упорядочить элементы в массиве по размеру в порядке убывания (называется values сейчас).
Извлечь counts из вашего hashmap (индексы теперь не имеют значения, потому что они нам больше не нужны, и массив соответствующим образом переупорядочен), а также упорядочьте их по убыванию.
Перебрать упорядоченный массив отсчетов и суммировать sum += counts[i] * values[i]

скажем, ваш массив

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

запросы:

q1: 1-3
q2: 2-4
q3: 3-5

карта:

1->1
2->2
3->3
4->2
5->1

отсчитано:

3,2,2,1

одно из совершенных переупорядочений (не имеет значения для алгоритма, поскольку требуется только сумма)

6,7,9,8,5,4,3,2,1,0

сумма для запросов:

(6 + 7 + 9) + (7 + 9 + 8) + (9 + 8 + 5) = 68

с алгоритмом:

3 * 9 + 2 * 8 + 2 * 7 + 1 * 6 + 1 * 5 = 68

(*) Если вы хотите ускорить это, вы можете использовать массив / вектор размера n вместо карты и использовать индексы в качестве ключей. Если бы просто упомянул карту в моем примере, потому что это делает идею более очевидной

1

Источник

user762567 18 июн '13 в 14:32

Другие вопросы по тегам c++ algorithm data-structures segment-tree

user2515024 18 июн '13 в 14:44 2013-06-18 14:44 · Accepted Answer · 2013-06-18 14:44

Концепция: "Вы должны зафиксировать самый большой элемент из массива в индексе, который запрашивается чаще всего, а затем второй по величине элемент во втором наиболее запрашиваемом элементе

Вот реализация моего метода:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
int main()
{
    LL n,q,l,r,i;
    cin>>n>>q;
    LL arr[n];
    for(i=0;i<n;i++)
        cin>>arr[i];
    LL freq[n];
    memset(freq,0,sizeof freq);
    sort(arr,arr+n);
    for(i=0;i<q;i++)
    {
        cin>>l>>r;
        freq[l-1]++; // DP method of freq
        if(r<n)     
        freq[r]--;
    }
    for(i=1;i<n;i++)
        freq[i]+=freq[i-1];
    sort(freq,freq+n);
    LL ans=0;
    for(i=n-1;i>=0;i--)
        if(freq[i])
            ans+=arr[i]*freq[i];
    cout<<ans<<endl;
    return 0;
}

Да, вы должны отсортировать массив, а затем отсортировать частоту, а затем умножить число на частоту, и это приведет к максимальной сумме.

Способ вести учет:

Не обновляйте каждый раз от li до ri.
вместо этого просто увеличьте счет в каждой начальной позиции и на одну более чем конечную позицию, потому что вы должны включить до конца.
наконец, сумма всех. в O(N). и вы можете знать, сколько раз каждый был увеличен. сортируйте его и сортируйте данный массив и умножайте число на полученную частоту, и вы получите ответ.

input: 5 3
array : 5 2 4 1 3
1st query: 1 5
freq update = 1 0 0 0 0 
2nd query: 2 3
freq update =1 1 0 -1 0 
3rd query: 2 3
freq update= 1 2 0 -2 0 
collective freq=1 3 3 1 1 
sorted freq= 1 1 1 3 3 
sorted array =1 2 3 4 5 
ans =33