Archie

这是一道主席树的题目

为什么这么说呢？因为根据推导，每个人的相对位置不变才是最优解

那么就涉及到每个人的位置位于1区间第几大了

当然每个人分开处理是可以的，不过一个权值线段树可以很好的帮助我们查询并且利用等差数列的性质来快速计算.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n,m;
int rt[5000001];
struct tr{
    int l;
    int r;
    int siz;
    int sum;
}tr[40000000];
int x;
int cnt;
void update(int ro){
    tr[ro].sum=tr[tr[ro].l].sum+tr[tr[ro].r].sum;
    tr[ro].siz=tr[tr[ro].l].siz+tr[tr[ro].r].siz;
}
void add(int &ro,int l,int r,int ke,int cop){
     ro=++cnt;
    tr[ro]=tr[cop];
    tr[ro].sum+=ke;
    tr[ro].siz+=1;
    if(l==r){
        return ;
    }
    int mid=(l+r)>>1;
    if(ke<=mid) add(tr[ro].l,l,mid,ke,tr[cop].l);
    else add(tr[ro].r,mid+1,r,ke,tr[cop].r);
//  update(ro);
    return ;
}
int l,r,k;
int que(int l,int r,int L,int R,int res,int pl){
    if(!(tr[r].siz-tr[l].siz)) return 0;
    int sum=tr[r].sum-tr[l].sum;
    int tot=tr[r].siz-tr[l].siz;
    if(L>=k+res) return sum-(2*k+2*res+tot-1)*tot/2;
    if(R<=k+res+tot-1) return (2*k+2*res+tot-1)*tot/2-sum;
    int mid=(L+R)>>1;
    int arr=tr[tr[r].l].siz-tr[tr[l].l].siz;
    return que(tr[l].l,tr[r].l,L,mid,res,k)+
            que(tr[l].r,tr[r].r,mid+1,R,res+arr,k);
}
signed main(){
    //rt[0]=1;
    read(n);read(m);
    for(int i=1;i<=n;++i){
        rt[i]=rt[i-1];
        read(x);
        add(rt[i],1,1000000,x,rt[i-1]);
    }
    for(int i=1;i<=m;++i){
        read(l);read(r);read(k);
        printf("%lld\n",que(rt[l-1],rt[r],1,1000000,0,k));
    }
    return 0;
}