1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
long long d[N], b[N], l[N], sum[N];
vector<int> v;
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    l[m+1]=n;
    for(int i=0; i<n; ++i) scanf("%d", &a[i]);
    sort(a, a+n);
    for(int i=n-1; i>=0; --i) sum[i]=sum[i+1]+a[i];
    v.push_back(0);
    for(int i=1; i<=m; ++i)
    {
        scanf("%lld%lld", &d[i], &b[i]);
        int lo=0, hi=v.size(), mid;
        long long res=0;
        while(lo+1!=hi)
        {
            mid=(lo+hi)/2;
            if(b[v[mid]]+(d[i]-d[v[mid]])*a[l[v[mid]]]<=b[i]) lo=mid;
            else hi=mid;
        }
        int num=lo;
        if(lo==v.size()-1) hi=n;
        else hi=l[v[lo+1]];
        lo=l[v[lo]]-1;
        while(lo+1!=hi)
        {
            mid=(lo+hi)/2;
            if(b[v[num]]+(d[i]-d[v[num]])*a[mid]<=b[i]) lo=mid;
            else hi=mid;
        }
        v.push_back(m+1);
        for(int j=v.size()-2; j>num; --j) res+=(d[i]-d[v[j]])*(sum[l[v[j]]]-sum[l[v[j+1]]])+(l[v[j+1]]-l[v[j]])*(b[v[j]]-b[i]);
        res+=(d[i]-d[v[num]])*(sum[hi]-sum[l[v[num+1]]])+(l[v[num+1]]-hi)*(b[v[num]]-b[i]);
        v.resize(num+1);
        if(l[v.back()]==hi) v.pop_back();
        if(res!=0) v.push_back(i);
        l[i]=hi;
        printf("%lld\n", res);
    }
    return 0;
}