[JSOI2018]列队（主席树）

跟上次那道列队不一样，但都是九条可怜。。。（吉老师太强了）

在主席树上统计答案，因为值域只有 \(10^6\) 甚至不用离散化。。。

\(Code\ Below:\)

#include <bits/stdc++.h>
#define int long long
using 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;
}