1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4  5 const int N=1e5+7; 6 int a[N],t,n,m,hsh[N],hsh_len,root[N],tot,x,y,pos,ic=1,k; 7 struct node{int l,r,sum;}T[N*40]; 8  9 inline int getid(int x){return lower_bound(hsh+1,hsh+1+hsh_len,x)-hsh;}10 inline int getd(int x){return upper_bound(hsh+1,hsh+1+hsh_len,x)-hsh-1;}11 12 void update(int &x,int y,int pos,int l=1,int r=n)13 {14     T[++tot]=T[y],T[tot].sum++,x=tot;15     if(l==r)return;16     int m=(l+r)>>1;17     if(pos<=m)update(T[x].l,T[y].l,pos,l,m);18     else update(T[x].r,T[y].r,pos,m+1,r);19 }20 21 int query(int x,int y,int pos,int l=1,int r=n)22 {23     if(l==r)return T[y].sum-T[x].sum;24     int m=(l+r)>>1;25     if(pos<=m)return query(T[x].l,T[y].l,pos,l,m);26     else return T[T[y].l].sum-T[T[x].l].sum+query(T[x].r,T[y].r,pos,m+1,r);27 }28 29 int main()30 {31     scanf("%d",&t);32     while(t--)33     {34         printf("Case %d:\n",ic++);35         scanf("%d%d",&n,&m),tot=0;36         F(i,1,n)scanf("%d",a+i),hsh[i]=a[i];37         sort(hsh+1,hsh+1+n),hsh_len=unique(hsh+1,hsh+1+n)-hsh-1;38         F(i,1,n)update(root[i],root[i-1],getid(a[i]));39         F(i,1,m)scanf("%d%d%d",&x,&y,&pos),printf("%d\n",(k=getd(pos))==0?0:query(root[x],root[y+1],k));40     }41     return 0;42 }