Luogu

LOJ

分析

显然，所有学生跑到指定位置后，相对位置不改变会最优。

那么最终会有一部分学生向左跑，一部分学生向右跑，而且两部分一定是分开的。

考虑建立一棵以位置为下标的主席树。

设 $rk_i$ 表示 $i$ 是当前区间中的学生中编号第 $rk_i$ 小的。若当前递归的区间是 $[l,r]$ ，分四种情况：

• 没有学生，直接返回 $0$ 。
• 全部向左跑，直接返回 $\sum a_i-\sum(k+rk_i-1)$ 。
• 全部向右跑，直接返回 $\sum(k+rk_i-1)-\sum a_i$ 。
• 两种都有，继续递归处理左右两个子区间。

在主席树上维护区间内人数和编号和即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10,L=1000000;

int n,m,a[N];

int rt[N],cnt=0;
struct node { int ls,rs,sz; ll sum; } t[N*25];
inline void modify(int& o,int f,int l,int r,int w) {
    t[o=++cnt]=t[f];
    if (l==r) { ++t[o].sz,t[o].sum+=w; return; }
    int mid=(l+r)>>1;
    if (w<=mid) modify(t[o].ls,t[f].ls,l,mid,w);
    else modify(t[o].rs,t[f].rs,mid+1,r,w);
    t[o].sz=t[t[o].ls].sz+t[t[o].rs].sz;
    t[o].sum=t[t[o].ls].sum+t[t[o].rs].sum;
}
inline ll query(int p,int q,int l,int r,int k,int s) {
    if (!(t[q].sz-t[p].sz)) return 0;
    int sz=t[q].sz-t[p].sz; ll sum=t[q].sum-t[p].sum;
    if (l>=k+s) return sum-1ll*(k+s+k+s+sz-1)*sz/2;
    if (r<=k+s+sz-1) return 1ll*(k+s+k+s+sz-1)*sz/2-sum;
    int mid=(l+r)>>1,lsz=t[t[q].ls].sz-t[t[p].ls].sz;
    return query(t[p].ls,t[q].ls,l,mid,k,s)
          +query(t[p].rs,t[q].rs,mid+1,r,k,s+lsz);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) modify(rt[i],rt[i-1],1,L,a[i]);
    while (m--) {
        int l=read(),r=read(),k=read();
        printf("%lld\n",query(rt[l-1],rt[r],1,L,k,0));
    }
    return 0;
}