Siano

Siano (线段树 \(\star\star\))

• 农夫 \(Byteasar\) 买了一片 \(n\) 亩的土地，他要在这上面种草。
• 他在每一亩土地上都种植了一种独一无二的草，其中，第 \(i\) 亩土地的草每天会长高 \(a_i\) 厘米。
• \(Byteasar\) 一共会进行 \(m\) 次收割，其中第 \(i\) 次收割在第 \(d_i\) 天，并把所有高度大于等于 \(b_i\) 的部分全部割去。
• \(Byteasar\) 想知道，每次收割得到的草的高度总和是多少，你能帮帮他吗？

Input

• 第一行包含两个正整数 \(n,m\) , 分别表示亩数和收割次数。
• 第二行包含 \(n\) 个正整数，其中第 \(i\) 个数为 \(a_i\)，依次表示每亩种植的草的生长能力。
• 接下来 \(m\) 行，每行包含两个正整数 \(d_i,b_i\) ，依次描述每次收割。

Output

• 输出 \(m\) 行，每行一个整数，依次回答每次收割能得到的草的高度总和。

Sample Input

4 4
1 2 4 3
1 1
2 2
3 0
4 4

Sample Output

6
6
18
0

Hint

• 样例解释
  • 第 \(1\) 天，草的高度分别为\(1,2,4,3\)，收割后变为\(1,1,1,1\)。
  • 第 \(2\) 天，草的高度分别为 \(2,3,5,4\)，收割后变为 \(2,2,2,2\)。
  • 第 \(3\) 天，草的高度分别为 \(3,4,6,5\)，收割后变为 \(0,0,0,0\)。
  • 第 \(4\) 天，草的高度分别为 \(1,2,4,3\) ，收割后变为 \(1,2,4,3\) 。
• 对于$ 100%$ 的数据，\(1\le n,m\le 5\times 10^5 ，1\le a_i\le 10^6，1\le d_i,b_i\le 10^{12}\)。
• 数据保证 \(d_1<d_2<...<d_m\)，并且任何时刻没有任何一亩草的高度超过 \(10^{12}\)。
• 来源：\(bzoj4293\)

分析

• 这个题嘛……大家的题解都说线段树，时限也开了30s明摆着告诉你是nlogn……

  不过我们发现a[i]<=10^6

  那么我就有一个以空间换时间的做法，并且只需要用很小的空间就可以把复杂度降到O(n)（或者说是O(maxa[i]+n)）

  首先，这个被收割的稻草的A值显然有单调性，换句话说，每次收割都会有一个左端点

  接着，我们发现，如果初始高度确定，生长时间确定，收割的门槛也确定，那么被收割的最低高度是可以算出来的

  那么我们可以搞个单调栈，然后搞一搞就做完了

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
#define N 1000006

using namespace std;
inline ll read(){
    ll ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while ('0'<=ch&&ch<='9'){
        ret=ret*10-48+ch;
        ch=getchar();
    }
    return ret;
}
int n;
ll a[N],s[N];
ll d[N/2],b[N/2],day;
int stk[N/2],top;
int to[N/2];
const int m=1e6;

int main(){
    n=read();day=read();
    for (int i=1;i<=n;++i) ++a[read()];
    for (int i=1;i<=day;b[i++]=read()) d[i]=read();
    s[0]=a[0]=0;
    for (int i=1;i<=m;++i) s[i]=s[i-1]+(ll)a[i]*i;
    for (int i=1;i<=m;++i) a[i]+=a[i-1];
    to[0]=d[0]=b[0]=0;
    top=0;stk[top++]=0;
    for (int k=1;k<=day;++k){
        ll res=0;
        int last=m,x=max((ll)to[stk[top-1]],min((b[k]-b[stk[top-1]])/(d[k]-d[stk[top-1]]),(ll)m));
        for (;x<last;x=max((ll)to[stk[top-1]],min((b[k]-b[stk[top-1]])/(d[k]-d[stk[top-1]]),(ll)m))){
            res+=(d[k]-d[stk[top-1]])*(s[last]-s[x])+(b[stk[top-1]]-b[k])*(a[last]-a[x]);
            if ((last=x)>to[stk[top-1]]) break;
            if (!--top) break;
        }
        if ((to[k]=last)<m) stk[top++]=k;
        printf("%lld\n",res);
    }
    return 0;
}