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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+5;
const int MAX=N;
struct query {
int l,r,h,id;
} q[N];
struct brick {
int h,pos;
} a[N];
int c[MAX],ans[N];
struct cmp {
template<typename T>
bool operator()(const T &a,const T &b)
{
return a.h<b.h;
}
};
void ins(int x,int d)
{
for (;x<MAX;x+=x&(-x)) {
c[x]+=d;
}
}
int query(int x)
{
int res=0;
for (;x;x-=x&(-x)) {
res+=c[x];
}
return res;
}
int main()
{
int T,n,m;
scanf("%d",&T);
for (int t=1;t<=T;t++) {
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) {
scanf("%d",&a[i].h);
a[i].pos=i;
}
for (int i=0;i<m;i++) {
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
q[i].id=i;
}
sort(a,a+n,cmp());
sort(q,q+m,cmp());
int k=0;
for (int i=0;i<m;i++) {
for (;k<n&&a[k].h<=q[i].h;k++)
ins(a[k].pos+1,1);
ans[q[i].id]=query(q[i].r+1)-query(q[i].l-1+1);
}
printf("Case %d:\n",t);
for (int i=0;i<m;i++)
printf("%d\n",ans[i]);
memset(c,0,sizeof(c));
}
return 0;
}
|
