#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 1e9;
struct SegmentTree {
int lc, rc; // 左右子节点编号
int sum;
} tree[N * 20];
int n, m, t, tot, a[N], b[N], root[N];
int build(int l, int r) {
int p = ++tot; // 新建一个节点，编号为p，代表当前区间[l,r]
tree[p].sum = 0;
if (l == r) return p;
int mid = (l + r) >> 1;
tree[p].lc = build(l, mid);
tree[p].rc = build(mid + 1, r);
return p;
}
int insert(int now, int l, int r, int x, int delta) {
int p = ++tot;
tree[p] = tree[now]; // 新建一个副本
if (l == r) {
tree[p].sum += delta; // 在副本上修改
return p;
}
int mid = (l + r) >> 1;
if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, delta);
else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, delta);
tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
return p;
}
int ask(int p,int q,int l,int r,int L,int R) {
if(l>=L&&r<=R)return tree[p].sum - tree[q].sum;
int mid = (l+r)>>1;
int sum=0;
if(R<=mid)sum += ask(tree[p].lc,tree[q].lc,l,mid,L,R);
else if(L>mid)sum += ask(tree[p].rc,tree[q].rc,mid+1,r,L,R);
else sum+= ask(tree[p].rc,tree[q].rc,mid+1,r,L,R) + ask(tree[p].lc,tree[q].lc,l,mid,L,R);
//L R
return sum;
}
int main() {
int Case;
scanf("%d", &Case);
for(int ccc=1; ccc<=Case; ++ccc) {
printf("Case %d:\n", ccc);
scanf("%d%d", &n,&m);
t=0;
tot=0;//!
memset(root,0,sizeof(root));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
++a[i];
b[++t] = a[i];
}
sort(b + 1, b + t + 1); // 离散化
t = unique(b + 1, b + t + 1) - (b + 1);
root[0] = build(1, t); // 关于离散化后的值域建树
for (int i = 1; i <= n; i++) {
int x = lower_bound(b + 1, b + t + 1, a[i]) - b; // 离散化后的值
root[i] = insert(root[i - 1], 1, t, x, 1); // 值为x的数增加1个
}
for (int i = 1; i <= m; i++) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
++l,++r,++k;
int x = lower_bound(b + 1, b + t + 1, k) - b;
if(x==t+1)--x;
if(b[x]>k)--x;
if(!x)printf("0\n");
else {
int ans = ask(root[r], root[l-1], 1, t, 1,x);
printf("%d\n", ans); // 从离散化后的值变回原值
}
}
}
return 0;
}
撰写