原题链接

思路过程

根据题意，可以很简单的想出一种暴力，在每一次询问时，都$O(n)$的扫一遍后的出答案。

显然，这样的暴力是超时的，但是我们通过这暴力可以想出一定的优化,显然，每亩草的顺序是不影响解题的，所以我们可以先将草的高度进行排序，使之具有单调性（在下面默认排为单调递增）。接下来在遍历时如果发现一个地方的草可以被割掉，那么在它之后的草也就一定都可以割掉，于是就可以用前缀和进行一步的优化。

但是显然这样子并没有优化多少，题目还是肯定过不了的。我们再思考一下，由于草的高度具有单调性，所以同一天被割去的草中寻找满足在这一天能被割的那一亩草地时可以用二分的思想。

但是只有在同一天被割掉的草中才能够用二分的方式，如何寻找符合条件的那一亩草还是个问题。因此，我们可以通过将在同一天被割去的草放入同一个块中，用类似于栈的思路进行查找，以及分块。

思路差不多就到这里结束了，再提一下我调了半个多小时的二分。

我原本是这么写的

while(l<r){
    int mid=(l+r)>>1;
    if(b[top].x+a[mid]*(d-b[top].d)>=x) r=mid;
    else l=mid+1;
    }

这个二分代码应该是对的，但是却过不去题目，我想了想，应该是当这一块的最右端不符合时，应取b[top].r+1向右的，而我的这个却会取到b[top].r。

因此我换了这种写法就过了：

while(l<r){
                int mid=(l+r+1)>>1;
                if(b[top].x+a[mid]*(d-b[top].d)<x) l=mid;
                else r=mid-1;
            }
            l=l+1;

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=5e5+10;
int n,m,top;
long long la,d,x;
long long a[N];

struct node{
    int l,r;
    long long d;
    long long x;
}b[N];
long long ans;
long long s[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
        b[++top].l=i;
        b[top].r=i;
        b[top].x=0;
        b[top].d=0;
    }
    for(int i=1;i<=m;i++){
        long long ans=0;
        scanf("%lld%lld",&d,&x);
        long long dd=d-la;

        if(b[top].x+a[b[top].r]*dd<x){
            printf("0\n");
            continue;
        }
        la=d;
        while(top&&b[top].x+a[b[top].l]*(d-b[top].d)>=x){
            ans+=(b[top].x)*(b[top].r-b[top].l+1);
            ans+=(d-b[top].d)*(s[b[top].r]-s[b[top].l-1]);
            top--;
        }
        if(top){
            int l=b[top].l,r=b[top].r;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(b[top].x+a[mid]*(d-b[top].d)<x) l=mid;
                else r=mid-1;
            }
            l=l+1;
            ans+=b[top].x*(b[top].r-l+1);
            ans+=(d-b[top].d)*(s[b[top].r]-s[l-1]);
            b[top].r=l-1;
            b[++top].l=l;
            b[top].r=n;
            b[top].x=x;
            b[top].d=d;
            ans-=(n-l+1)*x;
        }
        else{
            int l=1;
            b[++top].l=l;
            b[top].r=n;
            b[top].x=x;
            b[top].d=d;
            ans-=(n-l+1)*x;
        }
        printf("%lld\n",ans);
    }
}