显然是直接按照位置来排队最优

考虑每次是把编号一段拿出来，考虑建一颗主席树

可以在主席树上二分找到在$k$前的人要站到哪儿

注意有可能二分到的位置可能还是被放到

特判+1即可

然后随便算一下就可以了

#include
    
     using namespace std;#define ll long longinline int read(){
        char ch=getchar();    int res=0,f=1;    while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();    return res*f;}const int N=500005;const int M=1500005;const int Log=22;int n,m,sum[N*Log],lc[N*Log],rc[N*Log],rt[N];ll tr[N*Log],s[N],a[N],now,tot,pos;void update(int &u,int r1,int l,int r,ll k){
    	u=++tot,lc[u]=lc[r1],rc[u]=rc[r1],sum[u]=sum[r1]+1,tr[u]=tr[r1]+k;	if(l==r)return;int mid=(l+r)>>1;	if(k<=mid)update(lc[u],lc[r1],l,mid,k);	else update(rc[u],rc[r1],mid+1,r,k);}ll query(int r1,int r2,int l,int r){
    	if(l==r){
    		if(sum[r1]
     
      
       >1;ll del=sum[lc[r2]]-sum[lc[r1]];	if(!del)return query(rc[r1],rc[r2],mid+1,r);	if(mid<=now+del-1){
    		pos+=del,now+=del;		return query(rc[r1],rc[r2],mid+1,r)+tr[lc[r2]]-tr[lc[r1]];	}return query(lc[r1],lc[r2],l,mid);}inline ll calc(ll x,ll y){
    	return (x+y)*(y-x+1)/2;}signed  main(){
    	n=read(),m=read();	for(int i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+a[i],update(rt[i],rt[i-1],1,M-5,a[i]);	while(m--){
    		int l=read(),r=read(),k=read();		now=k,pos=0;		ll res=query(rt[l-1],rt[r],1,M-5);		cout<<(calc(k,k+pos-1)-res+s[r]-s[l-1]-res-calc(k+pos,k+r-l))<<'\n';	}}