【BZOJ5319】【JSOI2018】—军训列队（主席树）

传送门

显然是直接按照位置来排队最优
考虑每次是把编号一段拿出来，考虑建一颗主席树
可以在主席树上二分找到在$k$前的人要站到哪儿
注意有可能二分到的位置可能还是被放到
特判+1即可
然后随便算一下就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline 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]<sum[r2]&&l<now){
			pos++;return l;
		}
		return 0;
	}
	int mid=(l+r)>>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))<<'
';
	}
}