[bzoj 3343] 教主的魔法：分块

题意：维护一个长为N的数列，支持区间加、查询区间内大于等于C的数的个数。（N≤1000000，Q≤3000）

算是分块的模板题吧。分块很灵活，领会思想更加重要。

把长度为n的序列分为ceil(n/m)段，每段长m，最后一段可能例外。如果数组下标从0开始，则floor(i/m)即为i所在的块的编号，floor(i/m)*m为这一块的开始，min(floor(i/m)*m, n)为这一块结尾的下一个位置。

处理一个区间[l, r]，分为两种情况： 1. l、r在同一块内。 2. l、r不在同一块内。令lb=floor(l/m)，rb=floor(r/m)，此时[l, r]分为三部分：长度不大于m的一段[l, (lb+1)*m)、一些完整的块[(lb+1)*m, rb*m)、长度不大于m的一段[rb*m, r]。

维护每一块的信息，对一整块打标记或直接取用信息，对零散的暴力。

通常，m可以取。根据函数的特征做一些调整，也许能使最坏时间复杂度更优。比如，对这种形式，取可以使时间复杂度从降为。也可以做实验。

回到本题。把每一段拷贝一份并排序，通过二分查找统计一块的信息，遍历零散的部分，就能比较快速地回答询问。修改一整块可以通过打标记实现，零散的部分怎么办呢？原本想来个归并排序，然而首先得把这些数在排序后的数组中的位置找到，不如直接copy & sort。

修改的时间复杂度，查询的时间复杂度为，取。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 1e6, SIZE = 1e3, BLOCK = MAX_N/SIZE+1;
int N, Q, sz, blk, x[MAX_N], y[MAX_N], a[BLOCK];

inline void update(int l, int r) // [l, r)
{
	copy(x+l, x+r, y+l);
	sort(y+l, y+r);
}

inline void init()
{
	sz = sqrt(N);
	for (int i = 0; i < N; i += sz)
		update(i, min(i+sz, N));
}

void add(int l, int r, int w)
{
	int lb = l/sz, rb = r/sz, p = (lb+1)*sz, q = rb*sz, i;
	if (lb == rb) {
		for (i = l; i <= r; ++i)
			x[i] += w;
		update(q, min(q+sz, N));
	} else {
		for (i = l; i < p; ++i)
			x[i] += w;
		update(p-sz, p);
		for (int j = lb+1; i < q; ++j, i += sz)
			a[j] += w;
		for (; i <= r; ++i)
			x[i] += w;
		update(q, min(q+sz, N));
	}
}

int query(int l, int r, int w)
{
	int lb = l/sz, rb = r/sz, p = (lb+1)*sz, q = rb*sz, i, ans = 0;
	if (lb == rb) {
		for (i = l; i <= r; ++i)
			ans += a[lb]+x[i] >= w;
	} else {
		for (i = l; i < p; ++i)
			ans += a[lb]+x[i] >= w;
		for (int j = lb+1; i < q; ++j, i += sz)
			ans += y+i+sz - lower_bound(y+i, y+i+sz, w-a[j]);
		for (; i <= r; ++i)
			ans += a[rb]+x[i] >= w;
	}
	return ans;
}

int main()
{
	scanf("%d %d", &N, &Q);
	for (int i = 0; i < N; ++i)
		scanf("%d", &x[i]);
	init();
	for (int i = 0; i < Q; ++i) {
		char c;
		int l, r, w;
		scanf(" %c %d %d %d", &c, &l, &r, &w);
		--l;
		--r;
		if (c == 'M')
			add(l, r, w);
		else
			printf("%d\n", query(l, r, w));
	}
	return 0;
}