「突刺贯穿第二分块」P4117 [Ynoi2018] 五彩斑斓的世界

很帅气！

分块在线转离线，考虑每个块对于询问的贡献。
维护块的 max 和 tag 分别代表最大值和减了多少。

先考虑整块，
\(max < 2 * x：\) 每次暴力区间平移即可。
否则对于 \([1, x]\) 全部加上 \(x\) 平移到 \([x + 1, x * 2]\)，然后区间整体减 \(x\) 即可。
散块怎么做？暴力减，然后重构块就可以了。
那么我们怎么 听起来很简单是不是？可是怎么维护区间平移？我们发现在大量打 tag 的情况下，暴力不太好做。使用并查集即可。

复杂度显然直接用势能线段树那一套分析即可，注意我们要开两倍值域空间。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)

/*\yhx12243/ 鱼大保佑*/
/*「突刺贯穿第二分块」*/
using namespace std;

//#define getchar() (p1 == p2&&(p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

const int ___ = 1e6 + 5, __ = 5e5 + 5, _ = 1e5 + 5;
int n, m, bsz;
int a[___];

struct qry {
	int op, l, r, x, ans;
} q[__];

struct second_block {
	int l, r, mx, tag;
	int val[___], sz[_ + 1000], anc[___], rt[_];
	int find (int x) { return x == anc[x] ? x : anc[x] = find(anc[x]); }
	void build () {
		mx = tag = 0;
		rep(i, l, r) {
			mx = max(mx, a[i]);
			if (! rt[a[i]])
				anc[i] = rt[a[i]] = i, val[i] = a[i];
			else 
				anc[i] = rt[a[i]];
			sz[a[i]] ++;
		}
	}
	void merge (int x, int y) {
		if (rt[y]) anc[rt[x]] = rt[y];
		else {
			rt[y] = rt[x],
			val[rt[y]] = y;
		}
		sz[y] += sz[x], sz[x] = rt[x] = 0;
	} // x -> y
	void assign (int x) {
		if (mx - tag > (x << 1)) {
			rep(i, tag + 1, tag + x)
				if (rt[i]) merge(i, i + x);
			tag += x;
		} else {
			per(i, mx, tag + x + 1)
				if (rt[i]) merge(i, i - x);
			mx = min(mx, tag + x);
		}
	}
	void remake () {
		rep(i, l, r) {
			a[i] = val[find(i)], rt[a[i]] = sz[a[i]] = 0;
			a[i] -= tag;
		}
		rep(i, l, r) anc[i] = val[i] = 0;
	}
	void brute (int s, int t, int x) {
		int p = max(s, l), q = min(t, r);
		remake();
		rep(i, p, q) a[i] -= x * (a[i] > x);
		build();
	}
	void query (int x) {
		if (q[x].l <= l && r <= q[x].r) 
			q[x].ans += sz[q[x].x + tag];
		else {
			int s = max(q[x].l, l), t = min(q[x].r, r);
			rep(i, s, t) if (val[find(i)] - tag == q[x].x) q[x].ans ++;
		}
	}
} blk;
int main () {
	n = qread(), m = qread();
	rep(i, 1, n) a[i] = qread();
	rep(i, 1, m) {
		q[i].op = qread(), q[i].l = qread(), q[i].r = qread(), q[i].x = qread();
	}
	bsz = sqrt(n);
	for (int ptr = 1; ptr <= n; ptr += bsz) {
		blk.l = ptr, blk.r = ptr + bsz - 1;
		blk.build();
		rep(i, 1, m) {
			if (blk.r < q[i].l || q[i].r < blk.l) continue ;
			if (q[i].op == 1) {
				if (q[i].l <= blk.l && blk.r <= q[i].r)
					blk.assign(q[i].x);
				else blk.brute(q[i].l, q[i].r, q[i].x);
			} else if (blk.tag + q[i].x <= __) blk.query(i);
		}
		blk.remake();
	}
	rep(i, 1, m) if (q[i].op == 2) printf("%d\n", q[i].ans);
	return 0;
}