数列分块入门2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n , m , bel[maxn] , b[maxn] , len , a[maxn] , N , tag[maxn] , L[maxn] , R[maxn];
void Change(int p , int l , int r , int x)
{
	for (int i = l; i <= r; i++)a[i]+=x;
	for (int i = L[p]; i <= R[p]; i++)b[i]=a[i];
	sort(b + L[p] , b + R[p] + 1);
}
void Add(int l , int r , int x)
{
	int lp = bel[l] , rp = bel[r];
	if (lp == rp) 
	{
		Change(lp , l , r , x);
		return;
	}
	Change(lp , l , R[lp] , x);
	Change(rp , L[rp] , r , x);
	for (int i = lp + 1; i < rp; i++)tag[i]+=x;
	return;
}
int Query(int l , int r , int x)
{
	int res = 0;
	int lp = bel[l] , rp = bel[r];
	if (lp == rp)
	{
		for (int i = l; i <= r; i++) res+=(a[i] + tag[lp] < x);
		return res;
	}
	for (int i = l; i <= R[lp]; i++)res+=(b[i] + tag[lp] < x);
	for (int i = L[rp]; i <= r; i++)res+=(b[i] + tag[rp] < x);
	for (int i = lp + 1; i < rp; i++)res+=lower_bound(b + L[i] , b + R[i] + 1 , x - tag[i])-(b + L[i]);
	return res;
}
int main ()
{
//	freopen("in.txt" , "r" , stdin);
//	freopen("out.txt" , "w" , stdout);
	scanf("%d" , &n);
	len = sqrt(n);
	for (int i = 1; i <= n; i++)scanf("%d" , &a[i]),bel[i]=(i - 1)/len+1,b[i]=a[i];
	N = n / len; 
	if (n % len)N++;
	for (int i = 1; i <= N; i++)L[i]=R[i - 1] + 1 , R[i]=min(i * len , n) , sort(b + L[i] , b + R[i] + 1);
	for (int i = 1; i <= n; i++)
	{
		int op , l , r , c;
		scanf("%d%d%d%d" , &op , &l , &r , &c);
		if (op == 0)Add(l , r , c);
		else printf("%d\n" , Query(l , r , c * c));
	}
	return 0;
}