0

我正在尝试解决这个问题：

小女孩有一个包含 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;   
}

我的方法很简单，就像使用段树所说的那样，最后打印答案。

我的问题是有没有更简单的算法呢？还是我应该优化我的段树代码？

4

3 回答 3

1

我认为这会奏效 - 邀请评论

创建一个维度为 n 的数组，称为 count 并将其初始化为 0 遍历 Q 数组

对于每个查询 - 从 li 到 ri 将 count 增加 1，即元素的计数 li 到 ri 对数组进行排序 n 对 count 数组进行排序（记住索引） 取出计数中的最高值，并在相应的索引处放置最高元素N 对所有元素继续此操作

基本上，我们确保最高元素出现的次数最多（当被查询引用时）

于 2013-06-18T14:19:50.407 回答
1

这就是我要做的：

  1. 创建了一个（散列）映射索引->计数。遍历所有查询并为范围内的每个索引增加计数 (*)。
  2. 按大小对数组中的元素进行排序，降序（values现在称为）。
  3. 从您的哈希图中提取counts（索引现在无关紧要，因为我们不再需要它们，并且数组会相应地重新排序）并按降序排列。
  4. 遍历有序的计数数组并求和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 的数组/向量而不是映射，并使用索引作为键。如果只是在我的示例中提到了地图，因为它使想法更加明显

于 2013-06-18T14:32:05.213 回答
1

概念：“您必须将数组中的最大元素固定为查询次数最多的索引，然后将第二大元素固定为第二多查询的元素

这是我的方法的实现：

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

是的，您必须对数组进行排序，然后对频率进行排序，然后将数字乘以频率，这将导致最大和..

记数方法：

  1. 不要每次从 li 更新到 ri。
  2. 而是只增加每个起始位置的计数，并且比结束位置多一个，因为您必须包含直到结束。
  3. 最后总结所有计数。在 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
于 2013-06-18T14:44:35.397 回答