写在前面的扯淡：
分块的总体学习告一段落，这算是分块集中学习的最后一题么；以后当然也可能会写，就是零零散散的题了=。=
在洛谷上搜ynoi发现好像只有这道题和 由乃OI 2018 未来日记 是分块，久闻由乃OI之大名，就想试着写一写这道题(那道太毒了，写不了)；结果一开始差点被吓跑了，不过最后还是硬着头皮写完了QAQ
“分块最重要的就是常数” — —shadowice1984
好像挺有道理的，分块从诞生之日起就是一个依靠你的决策而决定复杂度的算法(或思想)，它不像什么高级的数据结构每块的写法都是基本固定的，复杂度有着严格的证明— —分块是个相对灵活的算法(所以也说它是一种思想)。举个例子：最简单的那种序列分块基本上复杂度都是$O(\frac{n^2}{size})$，$size$就是你自己决定的块大小，大家可能都知道块大小开$sqrt(n)$(当然这是均值不等式算出来的)，但是有时候可能某个操作的常数非常大，把块大小适当地调整可能会跑的更快......但是当卡常超过一定的地步，算法就又失去了本身的意义和美感......算了我语言表达能力太差了，还是赶快写题解吧=。=
考虑到区间一个个查询修改非常慢，先用并查集把每块里相同的数字连到第一次出现的位置上，然后考虑修改操作$(l,r,v)$：
对于一个最大值$maxx$不超过$2*v$的块，我们直接修改，即把大于$v$而小于最大值的部分的每个数$x$用并查集连到$x-v$
对于一个最大值$maxx$大于$2*v$的块，我们反过来修改，把小于$v$的部分的每个数$x$连到$x+v$，同时在区间上打标记
为什么要这样做？
首先我们发现这两种修改方法本质是一样的
然后我们发现对于第一种修改我们每次动的数是$v$级别的，同时我们把最大值缩小了$v$
而对于第二种修改我们每次动的数是$maxx-v$级别的，在那个限制下其实还是$v$级别的，和上面的效率是一样的(注意我们是根据$maxx$分出两种情况的，这也是用到了分块的思想)
然后均摊复杂度就有保证了，当然你还需要卡常(其实卡常不是很厉害，我就用了烂大街的快读+快输+register跑过去问题不大，还有这题当年在CF上好像因为CF太快+优化+3s实现把暴力放过去了=。=)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,Sq=,M=;
int a[N],ori[N],blo[N],ll[N],rr[N],aset[N];
int siz[N],maxx[Sq],laz[Sq],firs[Sq][N];
int n,m,t1,t2,t3,t4,sqr,cnt;
inline int read()
{
int ret=;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ret=(ret<<)+(ret<<)+(ch^),ch=getchar();
return ret;
}
void write(int x)
{
if(x>) write(x/);
putchar(x%+);
}
int finda(int x)
{
return (x==aset[x])?x:aset[x]=finda(aset[x]);
}
inline void rebuild(int b)//块重构
{
register int i;
for(i=ll[b];i<=rr[b];i++)
{
maxx[b]=max(maxx[b],a[i]);
firs[b][a[i]]=,aset[i]=i,siz[i]=;
}
for(i=ll[b];i<=rr[b];i++)//把每个数都并到第一次出现的位置
{
int &fir=firs[b][a[i]];
if(fir) siz[fir]+=siz[i],aset[i]=fir;
else fir=i,ori[i]=a[i];
}
}
inline void force(int b,int l,int r,int v)//大力重构
{
register int i;
for(i=ll[b];i<=rr[b];i++)
firs[b][a[i]=ori[finda(i)]]=;
for(i=l;i<=r;i++)
if(a[i]-laz[b]>v) a[i]-=v;
rebuild(b);
}
void change(int l,int r,int v)
{
register int i,j;
int b1=blo[l],b2=blo[r];
if(b1!=b2)
{
force(b1,l,rr[b1],v);
force(b2,ll[b2],r,v);
for(i=b1+;i<=b2-;i++)
if(maxx[i]-laz[i]<*v)//当最大值不超过2*v时，正常地修改
{
for(j=laz[i]+v+;j<=maxx[i];j++)
{
int &pos1=firs[i][j];
int &pos2=firs[i][j-v];
if(pos1)
{
if(pos2) siz[pos2]+=siz[pos1],aset[pos1]=pos2;
else pos2=pos1,ori[pos2]=j-v; pos1=;
}
}
maxx[i]=min(maxx[i],laz[i]+v);
}
else//否则反过来，把其余的数加上这个值并打标记
{
for(j=laz[i]+;j<=laz[i]+v;j++)
{
int &pos1=firs[i][j];
int &pos2=firs[i][j+v];
if(pos1)
{
if(pos2) siz[pos2]+=siz[pos1],aset[pos1]=pos2;
else pos2=pos1,ori[pos2]=j+v; pos1=;
}
}
laz[i]+=v;
}
}
else force(b1,l,r,v);
//修改的理论依据：对于第一种情况最大值在O(v)时间内减小了v，对于第二种情况最大值在O(max-v)减少了max-v，所以最终的均摊复杂度是O(1)的
//(虽然CF的官方题解这里写的是极差，但我觉得不太对，例如对233,235两个数来说，将大于234的数减去234后极差反而在增大)
}
int query(int l,int r,int v)//普通的查询
{
register int i;
int b1=blo[l],b2=blo[r],ret=;
if(b1!=b2)
{
for(i=l;i<=rr[b1];i++)
ret+=(ori[finda(i)]-laz[b1]==v);
for(i=ll[b2];i<=r;i++)
ret+=(ori[finda(i)]-laz[b2]==v);
for(i=b1+;i<=b2-;i++)
if(laz[i]+v<=M) ret+=siz[firs[i][laz[i]+v]];
}
else
for(i=l;i<=r;i++)
ret+=(ori[finda(i)]-laz[b1]==v);
return ret;
}
int main ()
{
register int i;
n=read(),m=read();
sqr=sqrt(n)+,ll[cnt=]=;
for(i=;i<=n;i++)
{
a[i]=read(),ori[i]=a[i];
aset[i]=i,blo[i]=(i-)/sqr+;
maxx[blo[i]]=max(maxx[blo[i]],a[i]);
if(i%sqr==) rr[cnt++]=i,ll[cnt]=i+;
}
rr[cnt]=n;
for(i=;i<=cnt;i++) rebuild(i);
for(i=;i<=m;i++)
{
t1=read(),t2=read(),t3=read(),t4=read();
if(t1==) change(t2,t3,t4); else printf("%d\n",query(t2,t3,t4));
}
return ;
}