由题目整理可得，$2 \times r_i>a$ 时，小球未进桶；$b \le 2 \times r_i \le a$ 时，小球进入桶中但最终未从桶中出去；$b>2 \times r_i$ 时，小球最终从桶中出去

本来我以为到这里就完了，但当我看到这个数据范围时，我就知道这题不简单，显然对于每次查询，你只能以 O(1) 的复杂度出答案，那么什么东西可以在预处理后以 O(1) 的复杂度出区间和呢？

废话，前缀和啊

#include<bits/stdc++.h>
using namespace std;
int r[2000060],qian[20005];
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>r[i];
		qian[2*r[i]]++;
	}
	for(int i=1;i<=20000;i++) qian[i]+=qian[i-1];
	for(int i=1;i<=q;i++){
		int a,b;
		cin>>a>>b;
		cout<<qian[20000]-qian[a]<<" "<<n-qian[b-1]-qian[20000]+qian[a]<<" "<<qian[b-1]<<endl;
	}
}

话说你一场比赛出两道前缀和真的好吗 ......