当前没有测试数据。

第二分块

题目大意

两种操作：

1. 区间大于 $x$ 的数减去 $x$。
2. 区间查 $x$ 的出现次数。

$1\le n\le 10^6$，$1\le m\le 5\times 10^5$，$1\le l\le r \le n$，$0 \le a_i,x \le 10^5+1$

时间限制 $7.50s$,内存限制 $64.00MB$

思路

看到 Ynoi 你想到什么？

分块、卡常。

实际上这题就是这么做的。

观察到内存限制很小，所以我们要写一个线性空间的做法。

关于只有 $2$ 操作的做法

首先，如果只有 $2$ 操作你会怎么做（必须分块，线性空间）？

你会发现如果开桶记录每块内每个数出现的次数的话空间是 $o(n^{1.5})$ 的，无法通过。

思考过后发现：某些数的贡献与另一些数没有关系（比如 0 2 0 4 0 中在 $[2,5]$ 有几个 $0$ 与 $a[1]$ 无关），所以可以把询问的答案拆成一些整块和一些散块的贡献的和。

lxl 出的题没有强制在线，所以考虑离线输入每个询问，枚举每一块，开桶记录这块内每个数出现的次数，然后枚举每个询问，看那些询问与这块管的区间有交集，可以分两种情况考虑：

1. 这块被询问区间包含，那直接查询桶，求出这块对这个询问的贡献
2. 这块不被询问区间包含，只与这块相交。那直接暴力求 $x$ 的出现次数。

现在分析这个做法的时空复杂度：

空间复杂度（$n,m,值域$ 同阶）：这个每块的桶因为不是同时使用，所以可以共用，空间 $O(n)$。存储询问和原数组是 $O(n)$，总空间复杂度 $O(n)+O(n)=O(n)$。

时间复杂度（$n,m,值域$ 同阶，块长设置为 $n^{0.5}$）：枚举每个块和每个询问的时间复杂度为 $O(n^{1.5})$，询问暴力求的部分数为 $O(n)$，每个最多枚举 $n^{0.5}$ 次，所以这里的时间复杂度为 $O(n^{1.5})$。总的时间复杂度为 $O(n^{1.5})+O(n^{1.5})=O(n^{1.5})$。

如果加入 $1$ 操作

下面的就是这道题的精华了。

先理解一下：区间大于 $x$ 的数减去 $x$ 就是区间小于等于 $x$ 的加上 $x$ 再全局减去 $x$。

还是之前的思路，看了 lxl 的题解后想到（对于每块）：

1. 对于区间最大值 $\le x\times 2$ 时，可以正常减去
2. 对于其他情况可以把 $[1,x]$ 上的值暴力加，然后打上块整体减的 $tag$。

枚举多少次，最大值减去最小值就缩小多少，所以对于每一块，$1$ 操作的时间复杂度是 $O(值域)$ 的。

还是类似上面的做法，看那些询问与这块管的区间有交集，可以分两种情况考虑：

1. 这块被询问区间包含，那直接修改。
2. 这块不被询问区间包含，只与这块相交，就把这块拆散

对于第二点，需要知道每个值最后变成了多少，可以用并查集记录。时间复杂度这里应用 mrsrz 大蛇的证明：

这里有一些很好的性质：我们每次用来连接的都是并查集的根，而一个根连到另一个根之后，这个值本身就消失了。而且我们在这里并不用这个并查集查询。因此这里的并查集并不会进行路径压缩，是 $O(1)$ 的。

拆散的次数是 $O(m)$ 的，所以总时间复杂度（$n,m,值域$ 同阶）$O(n^{1.5})$，可以通过。

$0$ 的处理

上面的思路可以通过原数据，但 $hack$ 过不了，是因为如果查询 $0$，则程序会输出错误答案。

因为1区间大于 $x$ 的数减去 $x$ 不会影响 $0$ 的个数，所以前缀和记录 $0$ 的个数，查询到就直接用前缀和相减求出答案。

代码

#include <bits/stdc++.h>
//#define int long long
#ifndef __linux__
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif

using namespace std;
	inline void Sr(int &a) {
		char ch = getchar_unlocked();
		while (ch < '0' || ch > '9') {
			ch = getchar_unlocked();
		}
		while (ch >= '0' && ch <= '9') {
			a = (a << 1) + (a << 3) + (ch ^ 48);
			ch = getchar_unlocked();
		}
	} inline void Sw(int a) {
		if (a == 0) {
			putchar_unlocked('0');
			return;
		}
		char ch[7];
		int till = 0;
		while (a) {
			ch[till++] = a % 10;
			a /= 10;
		}
		while (till)
			putchar_unlocked(ch[--till] ^ 48);
	}
int n, m;
int fa[100005];
int a[1000006];//每个数的值
bitset<500005> op;
int L[500005];
int R[500005];
int X[500005];
//上面四个数组是每个询问
int len;
int sum[100005];//桶
int ans[500005];//每个询问的答案
int maxx, y;//y是块内统一 -y

inline int cha(int x)
{
	if(fa[x]==fa[fa[x]]) return fa[x];
	while(x^fa[x])x=fa[x]=fa[fa[x]]=fa[fa[fa[x]]];
	return x;
}

inline void bin(int a, int b) {
	if (cha(a) ^ cha(b)) {
	fa[cha(a)] = cha(b);
	}
}//上面两个函数是并查集

inline void init(int l, int r) {//初始化
    memset(sum+y,0,4*(maxx-y+1));
	y = maxx = 0;
	for (int i = l; i <= r; ++i) {
        maxx = (maxx>a[i]?maxx:a[i]);
		sum[a[i]]++;
	}
	for (int i = 0; i <= maxx; ++i) {
		fa[i] = i;
	}
}

inline void ini(int l, int r) {//暴力拆散
	for (int i = l; i <= r; ++i) {
		while(a[i]^fa[a[i]])a[i]=fa[a[i]]=fa[fa[a[i]]]=fa[fa[fa[a[i]]]];
	}
}
int Sum[1000006];
int main() {
	Sr(n);Sr(m);
	for (int i = 0; i < n; ++i) {
		Sr(a[i]);
		if(a[i]==0){
			Sum[i+1]=1;
		}
		Sum[i+1]+=Sum[i];
	}
	for (int i = 0; i < m; ++i) {
		Sr(L[i]);
		op[i] = (L[i] == 2);
        L[i]=0;
		Sr(L[i]);Sr(R[i]);Sr(X[i]);
		if(op[i]&&X[i]==0){
			ans[i]=Sum[R[i]]-Sum[L[i]-1];
		}
		--L[i];
		--R[i];
	}
	len =max(1,min((int)sqrt(n*9/3),n));
	int t = n / len + min(1, n % len);//块的数量
	for (int e = 0; e < t; ++e) {
		int l = len * e;
		int r = min((e + 1) * len - 1, n - 1);
		init(l, r);
		for (int i = 0; i < m; ++i) {
			if (op[i]) {
				if(X[i]==0){
					continue;
				}
				if (X[i] > maxx - y) {
					continue;
				}
				if(L[i]>r||R[i]<l){
					continue;
				}
				if (!(L[i] <= l && R[i] >= r)) {//不是整块
					ini(l, r);
					for (int j = l; j <= r; ++j) {
						if (L[i] > j) 
							continue;
						if (R[i] < j) 
							break;
						if (a[j] - y == X[i]) 
							ans[i]++;
					}
					continue;
				}
				ans[i] += sum[X[i] + y];
			} else {
				if (X[i] >= maxx - y||L[i]>r||R[i]<l){
					continue;
				}
				if (!(L[i] <= l && R[i] >= r)) {//不是整块
					ini(l, r);
					for (int j = l; j <= r; ++j) {
						if (L[i] > j) 
							continue;
						if (R[i] < j) 
							break;
						if (a[j] - y > X[i]) {
							sum[a[j]]--;
							a[j] -= X[i];
							sum[a[j]]++;
						}
					}
					for (int i = maxx; i >= 0; --i) {
						if (sum[i]) {
							maxx = i;
							break;
						}
					}
					continue;
				}
				if ((X[i] << 1) <= maxx - y) {
					for (int j = y + 1; j <= y + X[i]; ++j) {
						sum[j + X[i]] += sum[j];
						sum[j] = 0;
						bin(j, j + X[i]);
					}
					y += X[i];
				} else {
					for (int j = maxx; j > y + X[i]; --j) {
						sum[j - X[i]] += sum[j];
						sum[j] = 0;
						bin(j, j - X[i]);
					}
					for (int i = maxx; i >= 0; --i) {
						if (sum[i]) {
							maxx = i;
							break;
						}
					}
				}
			}
		}
	}
	for (int i = 0; i < m; ++i) {
		if (op[i]) {
			Sw(ans[i]);
			putchar_unlocked('\n');
		}
	}
}

后记

这个代码是第五优解，如果你感兴趣可以拿这个代码试着卡最优解（反正我已经卡不动了，看我的用户名就知道我是分块新人）。