首先，对于一些同学，他们集合的顺序即为他们原来的顺序一定不劣。

每一个同学跑动距离：$| K+rk_i-1-a_i |$

考虑去绝对值，即考虑每一个同学向左还是向右跑。

从“导数”层面考虑 $K+rk_i-1-a_i$，由于两个同学不在同一个位置。所以 $1 \leq \Delta rk_i \leq \Delta a_i$。故其“导数”不大于 $0$。

故 $K+rk_i-1-a_i$ 是不上升的，所以我们可以通过区间两端点判断一个区间内同学的向左向右跑状态。

我们考虑在在权值线段树上分治：

  • 如果区间内没有同学，返回。
  • 如果区间内所有同学都向左跑，统计答案。
  • 如果区间内所有同学都向右跑，统计答案。
  • 否则，向下递归。

时间复杂度与在权值线段树上二分相同。

由于还有编号 $[l,r]$ 的限制，使用可持久化权值线段树即可。

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
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e5;
const int maxm=5e7;
const int tp=1e6;
struct Node{int ls,rs,sz;ll sm;};
int n,m;
int rt[maxn+5];
int tt;
Node T[maxm+5];
void Modify(int &x,int y,int L,int R,int p){
    T[x=++tt]=T[y];
    T[x].sz++,T[x].sm+=p;
    if(L==R) return;
    else{
        int mid=(R-L)/2+L;
        if(p<=mid) Modify(T[x].ls,T[y].ls,L,mid,p);
        else Modify(T[x].rs,T[y].rs,mid+1,R,p);
    }
}
ll Query(int x,int y,int L,int R,int K,int S){
    if(T[x].sz==T[y].sz) return 0;
    else{
        int cnt=T[y].sz-T[x].sz;
        ll sum=T[y].sm-T[x].sm;
        int mid=(R-L)/2+L;
        if(K+S+cnt-1-R>=0)
            return 1ll*cnt*(2*K+2*S+cnt-1)/2-sum;
        else if(K+S-L<=0)
            return sum-1ll*cnt*(2*K+2*S+cnt-1)/2;
        else{
            return Query(T[x].ls,T[y].ls,L,mid,K,S)
            +Query(T[x].rs,T[y].rs,mid+1,R,K
                ,S+T[T[y].ls].sz-T[T[x].ls].sz);
        }
    }
}
signed main(){
    int l,r,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        Modify(rt[i],rt[i-1],1,tp,x);
    }
    while(m--){
        scanf("%d%d%d",&l,&r,&x);
        printf("%lld\n",Query(rt[l-1],rt[r],1,tp,x,0));
    }
    return 0;
}