loj #6278. 数列分块入门 2 样例过了，一交满江红……

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e4 + 10;
const int MAXM = 240;

int a[MAXN], t[MAXN];

int len, tot;

int lp[MAXM], rp[MAXM], pos[MAXN];

ll add[MAXM];

inline 
void build(int n) {
	len = sqrt(n);
	tot = n / len + !!(n % len);
	for (int i = 1; i <= tot; i++) {
		lp[i] = (i - 1) * len + 1;
		rp[i] = i * len;
	}
	rp[tot] = n;
	for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
	for (int i = 1; i <= n; i++) t[i] = a[i];
	for (int i = 1; i <= tot; i++) sort(t + lp[i], t + rp[i] + 1);
}

inline 
void change(int l, int r, int k) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		for (int i = l; i <= r; i++) a[i] += k;
		return ;
	}
	for (int i = p + 1; i < q; i++) add[i] += k;
	for (int i = l; i <= rp[p]; i++) a[i] += k;
	for (int i = lp[q]; i <= r; i++) a[i] += k;
}

inline 
int query(int l, int r, int k) {
	int p = pos[l], q = pos[r];
	int ans = 0;
	if (p == q) {
		for (int i = l; i <= r; i++) {
			if (a[i] + add[p] < k) ans++;
		}
		return ans;
	}
	for (int i = p + 1; i < q; i++) {
		ans += upper_bound(t + lp[i], t + rp[p] + 1, k - add[i]) - t - lp[i];
	}
	for (int i = l; i <= rp[p]; i++) {
		if (a[i] + add[p] < k) ans++;
	}
	for (int i = lp[q]; i <= r; i++) {
		if (a[i] + add[q] < k) ans++;
	}
	return ans;
}

int n;

int opt, l, r, c;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	build(n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &opt, &l, &r, &c);
		if (opt) printf("%d\n", query(l, r, c * c));
		else change(l, r, c);
	}
}