Codeforces 276C Little Girl and Maximum Sum(线段树的区间更新)

客官°小女子只卖身不卖艺 2022-06-07 13:16 136阅读 0赞

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of *n*elements (the elements of the array are indexed starting from 1); also, there are *q*queries, each one is defined by a pair of integers *l**i*, *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ *n*). You need to find for each query the sum of elements of the array with indexes from *l**i* to *r**i*, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input

The first line contains two space-separated integers *n* (1 ≤ *n* ≤ 2·105) and *q* (1 ≤ *q* ≤ 2·105) — the number of elements in the array and the number of queries, correspondingly.

The next line contains *n* space-separated integers *a**i* (1 ≤ *a**i* ≤ 2·105) — the array elements.

Each of the following *q* lines contains two space-separated integers *l**i* and *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ *n*) — the *i*\-th query.

Output

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Example

Input

3 3
    5 3 2
    1 2
    2 3
    1 3

Output

Input

5 3
    5 2 4 1 3
    1 5
    2 3
    2 3

Output

题解：

题意：

给你一个长度为n的序列，你可以任意排序，然后在m个询问区间\[l,r\]内的和，最后累加这些和，让你求出能得到的和的最大值

思路：

一开始暴力模拟，华丽得tle了，然后换成了线段树就ac了，问了老刘他们说是看题解不用线段树用类似于树状数组的方法模拟也可以做出来。。。我说别人怎么a得那么快

我的思路：

就是先按从大到小对数组排序，然后就是用一颗全为0的线段树进行区间更新（要用lazy tag）每次区间内所有值+1，最后遍历所有不为0的子节点放进一个数组里面从大到小排序，最后两个数组相乘累加就是答案

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    #define INF 1008611111
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    int a[200005];
    int b[200005];
    int ans;
    int cmp(int x,int y)
    {
        return x>y;
    }
    struct node
    {
        int l,r;
        ll sum;
        int tag;
        int length()
        {
            return r-l+1;
        }
    }t[200005*4];
    void pushup(int k)
    {
        t[k].sum=t[lson].sum+t[rson].sum;
    }
    void pushdown(int k)
    {
        if(t[k].tag)
        {
            t[lson].sum+=t[lson].length()*t[k].tag;
            t[rson].sum+=t[rson].length()*t[k].tag;
            t[lson].tag+=t[k].tag;
            t[rson].tag+=t[k].tag;
            t[k].tag=0;
        }
    }
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].tag=0;
        if(l==r)
        {
            t[k].sum=0;
            return;
        }
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
        pushup(k);
    }
    void update(int l,int r,int k)
    {
        if(l==t[k].l&&r==t[k].r)
        {
            t[k].sum+=t[k].length();
            t[k].tag+=1;
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update(l,r,lson);
        else if(l>mid)
            update(l,r,rson);
        else
        {
            update(l,mid,lson);
            update(mid+1,r,rson);
        }
        pushup(k);
    }
    void query(int l,int r,int k)
    {
        if(t[k].sum==0)
            return;
        if(l==r)
        {
            b[ans]=t[k].sum;
            ans++;
            return;
        }
        int mid=M;
        pushdown(k);
        query(l,mid,lson);
        query(mid+1,r,rson);
    }
    int main()
    {
        int i,j,n,m,l,r;
        ll s=0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1,cmp);
        Build(1,n,1);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&l,&r);
            update(l,r,1);
        }
        ans=0;
        query(1,n,1);
        sort(b,b+ans,cmp);
        for(i=1;i<=n&&i-1<ans;i++)
        {
            s+=(ll)a[i]*b[i-1];
        }
        printf("%lld\n",s);
        return 0;
    }