1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<bits/stdc++.h>
#define REG register
#define MAXN 500005
#define MAXM 1000005
#define LL long long
using namespace std;
inline int read(){
REG int x(0);
REG char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
int n,m;
#define Ls(now) (t[now].ls)
#define Rs(now) (t[now].rs)
#define mid ((l+r)>>1)
int rt[MAXN],tot;
struct Tree{
LL S1,Sid;int ls,rs;
}t[MAXM<<6];
void Ins(int pre,int& now,int l,int r,int add){
now=++tot;
t[now]=t[pre];
t[now].S1++,t[now].Sid+=add;
if(l==r) return;
if(mid>=add) Ins(Ls(pre),Ls(now),l,mid,add);
else Ins(Rs(pre),Rs(now),mid+1,r,add);
}
LL Ask(int L,int R,int l,int r,int f,int k){
if(!(t[R].S1-t[L].S1)) return 0;
LL s1=t[R].S1-t[L].S1,sid=t[R].Sid-t[L].Sid;
if(l>=k+f) return sid-((((k<<1)+(f<<1)+s1-1)*s1)>>1);
if(r<=k+f+s1-1) return ((((k<<1)+(f<<1)+s1-1)*s1)>>1)-sid;
return Ask(Ls(L),Ls(R),l,mid,f,k)+Ask(Rs(L),Rs(R),mid+1,r,f+t[Ls(R)].S1-t[Ls(L)].S1,k);
}
int main(){
n=read(),m=read();
for(REG int i=1;i<=n;++i)
Ins(rt[i-1],rt[i],1,1000000,read());
while(m--){
int l=read(),r=read(),k=read();
printf("%lld\n",Ask(rt[l-1],rt[r],1,1000000,0,k));
}
}
|
