首先，感觉这个题很难用数据结构维护，所以可以想到分块（其实也是因为数据范围 \(10^5\) 比较小）。第一个想法可能是一个块内维护每一个不同的数出现了多少次，但是发现这样减一个数的时候很难合并，没办法优化。
然后就有一个事实，就是同一个块内当一起修改的时候，相同的数也一直会相同。所以我们如果把相同的数当成一样的，每一次只改动一个数就可以了。这个可以用并查集维护，合并就是并查集的 merge。然后发现这个时候我们如果还是 \(>x\) 的数暴力修改时间复杂度还是过不去。
有一个可能的想法是我们可以第二次分块。对于不同的数和不同的 \(x\)，有没有办法通过一些性质/单调性优化？有一个发现就是数的值域比较小，只有 \(10^5\)。就有了一个做法：
-
设 \(mx\) 为当前块的最大值，\(x\) 为要减去的数。
-
如果 \(2\cdot x\ge mx\)，我们就把所有 \(>x\) 的减去 \(x\)。因此我们可以用 \(\mathcal{O}(mx-x)\) 的复杂度使最大值减少了 \(\mathcal{O}(mx-x)\)。
-
如果 \(2\cdot x<mx\)，我们就把所有 \(\le x\) 的都加上 \(x\)。这里要维护一个懒标记，以后所有的都得减 \(x\)，因此我们可以用 \(\mathcal{O}(x)\) 的复杂度使最大值减少了 \(\mathcal{O}(x)\)。
因为 \(mx\) 不增，我们每一个块内的复杂度都是 \(\mathcal{O}(A)\) 的，因此这样总的复杂度就是 \(\mathcal{O}(n\sqrt{A})\) 的。
一些细节：
-
零散块直接重构。
-
不要像我一样
fa数组首先写了一个fa[B][N]的东西。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+5;
const int B = 320;
int n,m,bls,a[N],mx[N],v[N];
int fa[N],lb[B],rb[B],bl[N],tag[N];
struct node {
int rt,siz;
} g[B][N];
int ff(int x){
return x==fa[x]?x:fa[x]=ff(fa[x]);
}
void pu(int b){
for (int i=lb[b]; i<=rb[b]; i++){
a[i]=v[ff(i)];
g[b][a[i]].rt=0;
g[b][a[i]].siz=0;
a[i]-=tag[b];
}
tag[b]=0;
for (int i=lb[b]; i<=rb[b]; i++){
fa[i]=0;
}
}
void bd(int b){
mx[b]=0;
for (int i=lb[b]; i<=rb[b]; i++){
mx[b]=max(mx[b],a[i]);
g[b][a[i]].siz++;
if (g[b][a[i]].rt){
fa[i]=g[b][a[i]].rt;
}
else{
v[i]=a[i];
g[b][a[i]].rt=fa[i]=i;
}
}
}
void merge(int x,int a,int b){
auto &s=g[x][a];
auto &t=g[x][b];
if (t.rt){
fa[s.rt]=t.rt;
}
else{
t.rt=s.rt;
v[s.rt]=b;
}
t.siz+=s.siz;
s.siz=s.rt=0;
}
void at(int b,int ad){
if (ad<=mx[b]-tag[b]-ad){
for (int i=tag[b]+1; i<=tag[b]+ad; i++){
if (g[b][i].rt){
merge(b,i,i+ad);
}
}
tag[b]+=ad;
}
else{
for (int i=mx[b]; i>tag[b]+ad; i--){
merge(b,i,i-ad);
mx[b]=min(mx[b],tag[b]+ad);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++){
cin>>a[i];
}
for (int i=1; i<=n; i++){
bl[i]=(i-1)/B+1;
}
bls=1;
for (int i=1; (i-1)*B+1<=n; i++,bls++){
lb[i]=(i-1)*B+1;
rb[i]=min(n,i*B);
}
for (int i=1; i<=bls; i++){
bd(i);
}
while (m--){
int op,l,r,x;
cin>>op>>l>>r>>x;
if (op==1){
int il=bl[l],ir=bl[r];
pu(il);
if (il!=ir){
pu(ir);
}
if (il!=ir){
for (int i=l; i<=rb[il]; i++){
if (a[i]>x){
a[i]-=x;
}
}
for (int i=lb[ir]; i<=r; i++){
if (a[i]>x){
a[i]-=x;
}
}
for (int i=il+1; i<ir; i++){
at(i,x);
}
bd(il);
bd(ir);
}
else{
for (int i=l; i<=r; i++){
if (a[i]>x){
a[i]-=x;
}
}
bd(il);
}
}
else{
int il=bl[l],ir=bl[r],ans=0;
if (il!=ir){
for (int i=l; i<=rb[il]; i++){
if (v[ff(i)]-tag[il]==x){
ans++;
}
}
for (int i=lb[ir]; i<=r; i++){
if (v[ff(i)]-tag[ir]==x){
ans++;
}
}
for (int i=il+1; i<ir; i++){
if (x+tag[i]<=1e5){
ans+=g[i][x+tag[i]].siz;
}
}
}
else{
for (int i=l; i<=r; i++){
if (v[ff(i)]-tag[il]==x){
ans++;
}
}
}
cout<<ans<<"\n";
}
}
return 0;
}
``