WA #1 #2 #3 #4 #12 #13

#include<bits/stdc++.h>
using namespace std;
int n,m,nm,a[1000005],b[1000005],l[1005],r[1005],c[500005][4],maxn,tg,d[1000005],dd[200005],e[1000005],f[200005],ans[500005];
inline int find(int x)
{
	return x==d[x]?x:d[x]=find(d[x]);
}
inline int read()
{
	int result=0;
	char ch=getchar();
	while (ch<'0' || ch>'9')
	ch=getchar();
	while ('0'<=ch && ch<='9')
	{
		result=result*10+(ch^48);
		ch=getchar();
	}
	return result;
}
inline void write(int x)
{
    if (x>=10)
    write(x/10);
    putchar(x%10|48);
}
int main()
{
	n=read();
	m=read();
	nm=round(sqrt(n));
	for (register int i=1;i<=n;++i)
	{
		a[i]=read();
		b[i]=(i-1)/nm+1;
		if (l[b[i]]==0)
		l[b[i]]=i;
		r[b[i]]=i;
	}
	for (register int i=1;i<=m;++i)
	{
		c[i][0]=read();
		c[i][1]=read();
		c[i][2]=read();
		c[i][3]=read();
	}
	for (register int k=1;k<=b[n];++k)
	{
		maxn=0;
		tg=0;
		memset(dd,0,sizeof(dd));
		memset(f,0,sizeof(f));
		for (register int i=l[k];i<=r[k];++i)
		{
			maxn=max(maxn,a[i]);
			if (dd[a[i]])
			d[i]=dd[a[i]];
			else
			{
				d[i]=i;
				dd[a[i]]=i;
				e[i]=a[i];
			}
			++f[a[i]];
		}
		for (register int i=1;i<=m;++i)
		if (l[k]<=c[i][2] && c[i][1]<=r[k])
		{
			if (c[i][0]==1)
			{
				if (c[i][1]<=l[k] && r[k]<=c[i][2])
				{
					if (c[i][3]<<1<=maxn-tg)
					{
						for (register int j=tg+1;j<=c[i][3]+tg;++j)
						if (dd[j])
						{
							if (dd[j+c[i][3]])
							d[dd[j]]=dd[j+c[i][3]];
							else
							{
								dd[j+c[i][3]]=dd[j];
								e[dd[j+c[i][3]]]=j+c[i][3];
							}
							dd[j]=0;
							f[j+c[i][3]]+=f[j];
							f[j]=0;
						}
						tg+=c[i][3];
					}
					else
					{
						for (register int j=c[i][3]+tg+1;j<=maxn;++j)
						if (dd[j])
						{
							if (dd[j-c[i][3]])
							d[dd[j]]=dd[j-c[i][3]];
							else
							{
								dd[j-c[i][3]]=dd[j];
								e[dd[j-c[i][3]]]=j-c[i][3];
							}
							dd[j]=0;
							f[j-c[i][3]]+=f[j];
							f[j]=0;
						}
						maxn=min(maxn,c[i][3]+tg);
					}
				}
				else
				{
					maxn=0;
					tg=0;
					for (register int j=l[k];j<=r[k];++j)
					{
						a[j]=e[find(j)];
						dd[a[j]]=0;
						f[a[j]]=0;
						a[j]-=tg;
					}
					memset(e+l[k],0,r[k]-l[k]+1<<2);
					for (register int j=max(l[k],c[i][1]);j<=min(r[k],c[i][2]);++j)
					if (a[j]>c[i][3])
					a[j]-=c[i][3];
					for (register int j=l[k];j<=r[k];++j)
					{
						maxn=max(maxn,a[j]);
						if (dd[a[j]])
						d[j]=dd[a[j]];
						else
						{
							d[j]=j;
							dd[a[j]]=j;
							e[j]=a[j];
						}
						++f[a[j]];
					}
				}
			}
			else if (c[i][3]+tg<=200001)
			{
				if (c[i][1]<=l[k] && r[k]<=c[i][2])
				ans[i]+=f[c[i][3]+tg];
				else
				for (register int j=max(l[k],c[i][1]);j<=min(r[k],c[i][2]);++j)
				if (e[find(j)]-tg==c[i][3])
				++ans[i];
			}
		}
	}
	for (register int i=1;i<=m;++i)
	if (c[i][0]==2)
	{
		write(ans[i]);
		putchar('\n');
	}
}