换个角度思考

换个角度思考

Problem:

给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数
即对于询问 (l,r,x)，你需要输出 \(\sum_{i=l}^{r}[a_i \le x]\) 的值
其中 [exp] 是一个函数，它返回 1 当且仅当 exp 成立，其中 exp 表示某个表达式

Input:

第一行两个整数n,m
第二行n个整数表示序列a的元素，序列下标从1开始标号，保证1 ≤ ai ≤ 105
之后有m行，每行三个整数(l,r,k)，保证1 ≤ l ≤ r ≤ n，且1 ≤ k ≤ 105

Output:

对于每一个询问，输出一个整数表示答案后回车

Example:

Input

5 1
1 2 3 4 5
1 5 3

Output

3

Note

数据范围
\(1 ≤ n ≤ 10^5\)
\(1 ≤ m ≤ 10^5\)

题解：

离线+树状数组

对所有的询问进行离线处理，因为每次统计的都是比x小的数，所以用树状数组值域求解方法，求解区间内个数，这个类似于多个询问的区间值域问题。

Code：

/**********************************************************
* @Author: 			   Kirito
* @Date:   			   2020-08-06 17:49:37
* @Last Modified by:   Kirito
* @Last Modified time: 2020-08-06 18:05:43
* @Remark: 
**********************************************************/
#include 
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair pii;
typedef pair pll;

const int maxn=111111;
int sum[maxn<<2],n,m;
pii a[maxn];
int ans[maxn];

struct Ask
{
	int l,r,k,id;
	bool operator < (const Ask &mm) const{
		return this->k>n>>m;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		a[i]=make_pair(x,i);
	}
	std::vector vv;
	for(int i=0;i>l>>r>>x;
		vv.push_back(Ask{l,r,x,i});
	}
	sort(a+1,a+n+1);
	sort(vv.begin(),vv.end());
	int be=1;
	for(auto s:vv){
		while(a[be].first<=s.k&&be<=n){
			add(a[be].second);
			be++;
		}
		ans[s.id]=getAns(s.r)-getAns(s.l-1);
	}
	for(int i=0;i