换个角度思考

换个角度思考

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 <bits/stdc++.h>
#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<int,int> pii;
typedef pair<ll , ll> 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<mm.k;
	}
};

void add(int x)
{
	while(x<=n){
		sum[x]++;
		x+=lowbit(x);
	}
	return;
}

int getAns(int x)
{
	int ans=0;
	while(x){
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	#endif
	FAST;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		a[i]=make_pair(x,i);
	}
	std::vector<Ask> vv;
	for(int i=0;i<m;i++){
		int l,r,x;
		cin>>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<m;i++)
		cout<<ans[i]<<endl;
	return 0;
}