[BZOJ5319][主席树]JSOI2018：军训列队

BZOJ5319

首先，不动就可以站到队里面的人肯定不动
在集合点左边的人依次从左往右排
右边的人从右往左排
距离的计算有个绝对值不好去掉，但发现把休息点排序后满足单调性，就可以在主席树上二分了

Code：

#include<bits/stdc++.h>
#define ll long long
#define ls tr[k].l
#define rs tr[k].r
#define mid ((l+r)>>1)
const int M=500005;
const int N=1000005;
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
int n,m,tot,rt[M],ret,e=1e6;
struct seg{int l,r,size;ll sum;}tr[N*21];
void build(int x,int l,int r,int &k){
    tr[++tot]=tr[k];k=tot;++tr[k].size;tr[k].sum+=x;
    if(l==r)return;
    if(mid>=x) build(x,l,mid,ls);
	else build(x,mid+1,r,rs);
}
ll qsum(int i,int j,int L,int R,int l,int r){
    if(l>R || r<L) return 0;
    if(l==L && r==R) return tr[j].sum-tr[i].sum;
    if(mid>=R) return qsum(tr[i].l,tr[j].l,L,R,l,mid);
    else if(mid<L) return qsum(tr[i].r,tr[j].r,L,R,mid+1,r);
    else return qsum(tr[i].l,tr[j].l,L,mid,l,mid)+qsum(tr[i].r,tr[j].r,mid+1,R,mid+1,r);
}
void qkth(int i,int j,int k,int l,int r,int rnk){
    if(tr[j].size-tr[i].size==0) return;
    if(l==r){
        ++rnk;
        if(l<=k+rnk-1) ret=rnk;
        return;
    }
    int lsz=tr[tr[j].l].size-tr[tr[i].l].size;
    if(mid<=k+rnk+lsz-1){
        ret=rnk+lsz;
        qkth(tr[i].r,tr[j].r,k,mid+1,r,rnk+lsz);
    }
    else qkth(tr[i].l,tr[j].l,k,l,mid,rnk);
}
int lll,rrr,k,l,r,sz;ll ans=0;
int main(){
    n=read();m=read();e+=n;
    for(int i=1,x;i<=n;i++){
        x=read();rt[i]=rt[i-1];
        build(x,0,e,rt[i]);
    }
    while(m--){
        lll=read();rrr=read();k=read();ret=ans=0;sz=rrr-lll+1;
        qkth(rt[lll-1],rt[rrr],k,0,e,0);
        ans+=(ll)(2*(ll)k+ret-1)*ret/2-qsum(rt[lll-1],rt[rrr],0,k+ret-1,0,e)+qsum(rt[lll-1],rt[rrr],k+ret,e,0,e)-(ll)(2*(ll)k+ret+sz-1)*(sz-ret)/2;
        printf("%lld\n",ans);
    }
    return 0;
}