突刺贯穿的第二分块

[CF896E] Welcome home, Chtholly

给定一个长为 \(n\) 的序列 \(a_1\sim a_n\)，\(m\) 次操作，分两种：

• 1 l r x，将 \(a_l\sim a_r\) 中 \(\gt x\) 的数减去 \(x\)。

• 2 l r x，询问此时 \(a_l\sim a_r\) 有多少数等于 \(x\)。

\(1\le n,m,a_i,x\le 10^5\)。

lxl 的分块科技，很奇妙。

考虑根据这个特殊的值域搞点什么东西。

分块以后可以直接在每个块内开 \(10^5\) 个桶存这个块里的数。这样询问操作就可以解决了。

考虑修改操作，散块重构，对于整块，两种暴力：

• 给 \(\le x\) 的数加上 \(x\)，然后给整个块打上一个整体减 \(x\) 的 tag。

• 枚举 \(\gt x\) 的桶 \(i\)，将桶 \(i\) 和 \(i-x\) 合并。

单次操作 \(\mathcal O(V)\)，这是坏的。考虑平衡思想，将两者结合。记录整块最大值 \(\rm maxv\)，分类：

• \(\mathrm{maxv}\le 2x\)，采用暴力 2.

• \(\mathrm{maxv}\gt 2x\)，采用暴力 1.

相当于用 \(\mathcal O(Dx)\) 的代价使得 \(\rm maxv\) 减小了 \(x\)。总复杂度 \(\mathcal O(Dn\sqrt n)\)，这是好的。

考虑用一个 \(\mathcal O(1)\) 复杂度的数据结构维护桶的合并。使用并查集，因为每条边至多被遍历一遍，单次复杂度均摊 \(\mathcal O(1)\)。

强化版卡空间，可以离线，对于每个块单独计算对所有询问的贡献。

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
const int S = 400;

int read() {
	int s = 0;
	char c = getchar();
	for(;c < '0'||c > '9';c = getchar());
	for(;c >= '0'&&c <= '9';c = getchar())
		s = (s << 1) + (s << 3) + (c ^ '0');
	return s;
}

void print(int x) {
	if(x > 9)
		print(x / 10);
	putchar(x % 10 + '0');
	return ;
}

int pre[maxn],val[maxn];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

struct node {
	int rt,sz;
	node() {
		rt = sz = 0;
	}
} d[S + 5][maxn];

int max(const int& x,const int& y) {
	return x > y ? x : y;
}

int min(const int& x,const int& y) {
	return x < y ? x : y;
}

int n,m,a[maxn],t,maxv[S],L[S],R[S],pos[maxn],tag[S];

void pushdown(int p) {
	for(int i = L[p];i <= R[p];++ i)
		a[i] = val[find(i)],d[p][a[i]].rt = d[p][a[i]].sz = 0,a[i] -= tag[p];
	tag[p] = 0;
	for(int i = L[p];i <= R[p];++ i)
		pre[i] = 0;
	return ;
}

void Maintain(int p) {
	maxv[p] = 0;
	for(int i = L[p];i <= R[p];++ i) {
		maxv[p] = max(maxv[p] , a[i]);
		++ d[p][a[i]].sz;
		if(!d[p][a[i]].rt)
			d[p][a[i]].rt = pre[i] = i,val[i] = a[i];
		else
			pre[i] = d[p][a[i]].rt;
	}
	return ;
}

void Merge(int p,int x,int y) {
	if(d[p][y].rt)
		pre[d[p][x].rt] = d[p][y].rt;
	else
		d[p][y].rt = d[p][x].rt,val[d[p][x].rt] = y;
	d[p][y].sz += d[p][x].sz;
	d[p][x].sz = d[p][x].rt = 0;
	return ;
}

void gettag(int p,int x) {
	if(maxv[p] - tag[p] < (x << 1)) {
		for(int i = maxv[p];i > x + tag[p];-- i)
			if(d[p][i].rt)
				Merge(p , i , i - x);
		maxv[p] = min(maxv[p] , x + tag[p]);
	}
	else {
		for(int i = tag[p] + 1;i <= x + tag[p];++ i)
			if(d[p][i].rt)
				Merge(p , i , i + x);
		tag[p] += x;
	}
	return ;
}

void modify(int l,int r,int x) {
	int p = pos[l],q = pos[r];
	if(p == q) {
		pushdown(p);
		for(int i = l;i <= r;++ i)
			if(a[i] > x)
				a[i] -= x;
		Maintain(p);
	}
	else {
		pushdown(p);
		pushdown(q);
		for(int i = l;i <= R[p];++ i)
			if(a[i] > x)
				a[i] -= x;
		for(int i = L[q];i <= r;++ i)
			if(a[i] > x)
				a[i] -= x;
		Maintain(p);
		Maintain(q);
		for(int i = p + 1;i < q;++ i)
			gettag(i , x);
	}
	return ;
}

int query(int l,int r,int x) {
	int ans = 0,p = pos[l],q = pos[r];
	if(p == q) {
		for(int i = l;i <= r;++ i)
			if(val[find(i)] - tag[p] == x)
				++ ans;
	}
	else {
		for(int i = l;i <= R[p];++ i)
			if(val[find(i)] - tag[p] == x)
				++ ans;
		for(int i = L[q];i <= r;++ i)
			if(val[find(i)] - tag[q] == x)
				++ ans;
		for(int i = p + 1;i < q;++ i)
			if(x + tag[i] <= 100000)
				ans += d[i][x + tag[i]].sz;
	}
	return ans;
}

int main() {
	n = read();
	m = read();
	for(int i = 1;i <= n;++ i)
		a[i] = read(),pos[i] = (i - 1) / S + 1;
	for(int i = 1;i <= n;++ i) {
		if(!L[pos[i]])
			L[pos[i]] = i;
		R[pos[i]] = i;
	}
	for(int i = 1;i <= pos[n];++ i)
		Maintain(i);
	while(m --) {
		int op = read(),l = read(),r = read(),x = read();
		if(op == 1)
			modify(l , r , x);
		else
			print(query(l , r , x)),putchar('\n');
	}
	return 0;
}