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

在主席树上统计答案，因为值域只有 \(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;}