跟上次那道列队不一样，但都是九条可怜。。。（吉老师太强了）
在主席树上统计答案，因为值域只有 \(10^6\) 甚至不用离散化。。。
\(Code\ Below:\)
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn=500000+10;const int lim=1000000;const int inf=0x3f3f3f3f;int n,m,a[maxn],Sum[maxn],ans,T[maxn],L[maxn<<5],R[maxn<<5],sum[maxn<<5],siz[maxn<<5],cnt;inline int read(){ ???register int x=0,f=1;char ch=getchar(); ???while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} ???while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} ???return (f==1)?x:-x;}void update(int &now,int pre,int l,int r,int x){ ???now=++cnt;L[now]=L[pre];R[now]=R[pre]; ???sum[now]=sum[pre]+x;siz[now]=siz[pre]+1; ???if(l == r) return ; ???int mid=(l+r)>>1; ???if(x <= mid) update(L[now],L[pre],l,mid,x); ???else update(R[now],R[pre],mid+1,r,x);}int query(int u,int v,int Le,int Ri,int l,int r){ ???if(Le > Ri) return 0; ????if(r <= Ri) return (Le+Ri)*(Ri-Le+1)/2-(sum[v]-sum[u]); ???if(Le <= l) return (sum[v]-sum[u])-(Le+Ri)*(Ri-Le+1)/2; ???int mid=(l+r)>>1,cnt=siz[L[v]]-siz[L[u]]; ???return query(L[u],L[v],Le,Le+cnt-1,l,mid)+query(R[u],R[v],Le+cnt,Ri,mid+1,r);}signed main(){ ???n=read(),m=read(); ???for(int i=1;i<=n;i++){ ???????a[i]=read(); ???????update(T[i],T[i-1],1,lim,a[i]); ???} ???int l,r,k; ???while(m--){ ???????l=read(),r=read(),k=read(); ???????printf("%lld\n",query(T[l-1],T[r],k,k+r-l,1,lim)); ???} ???return 0;}[JSOI2018]列队（主席树）
原文地址：https://www.cnblogs.com/owencodeisking/p/10228919.html