#P10814. 【模板】离线二维数点

【模板】离线二维数点

题目背景

青蛙。

题目描述

给你一个长为 nn 的序列 aa,有 mm 次询问,每次询问给定 l,r,xl,r,x,求 [l,r][l,r] 区间中小于等于 xx 的元素个数。

输入格式

第一行两个数 n,mn,m

第二行 nn 个数表示序列 aa

之后 mm 行,每行三个数 l,r,xl,r,x 表示一次询问。

输出格式

对每个询问,输出一行一个数表示答案。

6 4
1 1 4 5 1 4
1 6 3
1 6 4
1 1 4
1 5 4
3
5
1
4

提示

对于 20%20\% 的数据,满足 1n,m,ai,l,r,x1001\le n,m,a_i,l,r,x\le 100

对于 40%40\% 的数据,满足 1n,m,ai,l,r,x1041\le n,m,a_i,l,r,x\le 10^4

对于 60%60\% 的数据,满足 1n,m,ai,l,r,x1051\le n,m,a_i,l,r,x\le 10^5

对于 80%80\% 的数据,满足 1n,m,ai,l,r,x1061\le n,m,a_i,l,r,x\le 10^6

对于 100%100\% 的数据,满足 1n,m,ai,l,r,x2×1061\le n,m,a_i,l,r,x\le 2\times10^6