不管怎么修改，所有数字的排名都不会发生变化。

将a[]从小到大排序之后，维护一棵线段树，在上面修改。

对于收割操作，在线段树上二分，找到需要修改的后缀进行区间赋值即可。

时间复杂度$O(m\log n)$。

 

#include
     
      #include
      
       #define N 1050000typedef long long ll;int n,m,i,a[N/2];ll now,old,R,ans;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10LL)+=c-'0';}struct P{  bool a;ll b,c;  P(){a=1,b=c=0;}  P(bool _a,ll _b,ll _c){a=_a,b=_b,c=_c;}  P operator+(P B){return P(a&B.a,b*B.a+B.b,c*B.a+B.c);}}tag[N];struct Node{ll vl,vr,vs,s;}T[N];inline void add(int x,P p,int a,int b){  if(p.a){    T[x].vl+=p.b+p.c*::a[a];    T[x].vr+=p.b+p.c*::a[b];    T[x].vs+=p.b*(b-a+1)+p.c*T[x].s;  }else{    T[x].vl=p.b+p.c*::a[a];    T[x].vr=p.b+p.c*::a[b];    T[x].vs=p.b*(b-a+1)+p.c*T[x].s;  }  tag[x]=tag[x]+p;}inline void pb(int x,int a,int b){  int mid=(a+b)>>1;  add(x<<1,tag[x],a,mid),add(x<<1|1,tag[x],mid+1,b);  tag[x]=P();}void build(int x,int a,int b){  if(a==b){T[x].s=::a[a];return;}  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);  T[x].s=T[x<<1].s+T[x<<1|1].s;}void check(int x,int a,int b){  if(T[x].vr<=R)return;  if(T[x].vl>R){    ans+=T[x].vs-R*(b-a+1);    add(x,P(0,R,0),a,b);    return;  }  pb(x,a,b);  int mid=(a+b)>>1;  check(x<<1,a,mid),check(x<<1|1,mid+1,b);  T[x].vl=T[x<<1].vl,T[x].vr=T[x<<1|1].vr;  T[x].vs=T[x<<1].vs+T[x<<1|1].vs;}int main(){  for(read(n),read(m),i=1;i<=n;i++)read(a[i]);  std::sort(a+1,a+n+1);  build(1,1,n);  while(m--){    read(now),read(R);    add(1,P(1,0,now-old),1,n);    ans=0;    check(1,1,n);    old=now;    printf("%lld\n",ans);  }  return 0;}