分塊二分：

眾所周知，分塊可以實現一些奇奇怪怪的區間的問題，比如以下這個題：
給定一個 \(N\) 和 \(N\) 個整數，分別為 \(A_1,A_2,A_3,A_4....A_N\) 每次詢問給出三個整數 \(l,r,k\) 求所有滿足 \(l \leq i \leq r,a_i \leq k\) 的個數。
不難想到暴力，可以做到每次操作 \(N \log_2 N\) 總計 \(MN \log_2 N\) 但這樣的復雜度在 \(N,M \leq 100000\) 時是不容易過掉的。因此考慮優化它。
如果用分塊該如何實現呢？
可以把每一個塊內的元素排序，然后整塊時直接二分答案，散塊暴力處理，這樣就能將時間復雜度降至 \(O(Q\sqrt N \log_2 N)\) 但這樣是不容易過的，因此繼續考慮優化它，不難想到，當整塊時，塊長越大，\(\log_2 (r-l+1)\) 是基本不變的，但是可以減少塊的數量，因此我們可以將塊長設為 \(N/\sqrt{N\log N}\) 這樣做復雜度可以近似 \(O(N\sqrt{Q \log_2 N})\) 可以通過此題。

樣例：
block.in

5 3
1 2 3 4 5
1 5 3
1 4 3
2 5 2

block.out

3
3
1

代碼：

//writer : tomxi  
#include<cstdio>
#include<algorithm>
#include<iostream>

using std::sort;
const int N=1e5+5;
const int K=300;
int a[N],d[N],n,q,l,r,left,right,lk,rk,belong[N],L[K],R[K],len,k;

inline int query(int lf,int rt,int val){
	lk=belong[lf],rk=belong[rt];
	int ans=0;
	if(lk==rk){
		for(int i=lf;i<=rt;i++) if(a[i]<=val) ans++;
		return ans;
	}
	for(int i=lf;i<L[lk+1];i++) if(a[i]<=val) ans++;
	for(int i=rt;i>R[rk-1];i--) if(a[i]<=val) ans++;
	for(int i=lk+1;i<=rk-1;i++){
		left=L[i],right=R[i];
		int res=0;
		while(left<=right){
			int mid=(left+right)>>1;
			if(d[mid]<=k){
				res=mid-L[i]+1;
				left=mid+1;
			}else{
				right=mid-1;
			}
		}
		ans+=res;
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&q);
	len=sqrt(n*25);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) d[i]=a[i];
	for(int i=1;i<=n;i++) belong[i]=(i-1)/len+1; 
	for(int i=1,j=n;i<=n;i++,j--){
		R[belong[i]]=i;L[belong[j]]=j;
	}	
	for(int i=belong[1];i<=belong[n];++i) sort(d+L[i],d+R[i]+1);
	while(q--){
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",query(l,r,k));
	}
	return 0;
}