分块入门 $2$ ，块内排序查询 $k$ 大值

虽然有板子但是自己乱 $yy$ 了半天

复杂度大概是 $O(m \sqrt{n} \log ({\sqrt{n}}))$ 的样子。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define int long long

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 50010;
int w[N], len, add[N], n;
vector<PII> b[N];

int get(int x) {
	return x / len;
}

int query_block(int k, int v) {
	if (b[k][0].x >= v) return 0;
	int l = 0, r = b[k].size() - 1;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (b[k][mid].x >= v) r = mid - 1;
		else l = mid;
	}
	return l + 1;
}

void modify(int l, int r, int v) { // 将 [l, r] 内的元素加 v , 复杂度 O(sqrt(n) * log(sqrt(n)))  
	if (get(l) == get(r)) {
		int u = get(l);
		for (int i = 0; i < b[u].size(); i ++ )
			if (b[u][i].y >= l && b[u][i].y <= r)
				b[u][i].x += v;
		sort(b[u].begin(), b[u].end());
		return;
	}
	int i = l, j = r;
	int u = get(l);
	for (int i = 0; i < b[u].size(); i ++ )
		if (b[u][i].y >= l) b[u][i].x += v;
	sort(b[u].begin(), b[u].end());
	u = get(r);
	for (int i = 0; i < b[u].size(); i ++ )
		if (b[u][i].y <= r) b[u][i].x += v;
	sort(b[u].begin(), b[u].end());
	if (get(l) + 1 > get(r) - 1) return;
	for (int i = get(l) + 1; i <= get(r) - 1; i ++ )
		add[i] += v;
}

int query(int l, int r, int v) { // 查询区间 [l, r] 内小于 v 的数的个数 
	int res = 0;
	if (get(l) == get(r)) {
		int u = get(l);
		for (int i = 0; i < b[u].size(); i ++ )
			if (b[u][i].y >= l && b[u][i].y <= r)
				res += (b[u][i].x + add[u] < v);
		return res;
	}
	
	int u = get(l);
	for (int i = 0; i < b[u].size(); i ++ )
		if (b[u][i].y >= l)
			res += (b[u][i].x + add[u] < v);
	u = get(r);
	for (int i = 0; i < b[u].size(); i ++ )
		if (b[u][i].y <= r)
			res += (b[u][i].x + add[u] < v);
	if (get(l) + 1 > get(r) - 1) return res;
	for (int i = get(l) + 1; i <= get(r) - 1; i ++ )
		res += query_block(i, v - add[i]);
	return res;
}

signed main() {
//	freopen("a2.in", "r", stdin);
	
	scanf("%lld", &n);
	len = sqrt(n);
	
	for (int i = 1; i <= n; i ++ )
		scanf("%lld", &w[i]);
	
	for (int i = 1; i <= n; i ++ )
		b[get(i)].push_back({w[i], i});
		
	for (int i = 1; i <= n; i ++ ) {
		int op, l, r, c;
		scanf("%lld%lld%lld%lld", &op, &l, &r, &c);
		
		if (op == 0) 
			modify(l, r, c);
		else 
			printf("%lld\n", query(l, r, c * c));
	}
	
	return 0;
}