RT

#include<iostream>
#include<math.h>
using namespace std;
int n,m,t,len;
int a[1000005],pos[1000005],uf[1000005];
int rt[100005],size[100005];
int q[500005][5],ans[500005];
int l[1005],r[1005],Max[1005],lazy[1005];
int uf_ask(int x)
{
	if(uf[x]==x)
	{
		return x;
	}
	else
	{
		uf[x]=uf_ask(uf[x]);
		return uf[x];
	}
}
int main()
{
    cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		ans[i]=-1;
	}
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
    	for(int j=1;j<=4;j++)
    	{
    		cin>>q[i][j];
		}
	}
    len=sqrt(n);
    t=n/len;
    if(n%len!=0)
    {
        t++;
    }
    for(int i=1;i<=t;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    if(r[t]>n)
    {
        r[t]=n;
    }
    for(int i=1;i<=t;i++)
    {
    	for(int j=0;j<=100000;j++)
    	{
    		size[j]=0;
    		rt[j]=0;
		}
    	for(int j=l[i];j<=r[i];j++)
    	{
    		Max[i]=max(Max[i],a[j]);
    		uf[j]=j;
    		size[a[j]]++;
    		if(rt[a[j]])
    		{
    			uf[j]=rt[a[j]];
			}
			else
			{
				rt[a[j]]=j;
			}
		}
    	for(int j=1;j<=m;j++)
    	{
    		if(q[j][1]==1)
    		{
    			if(q[j][2]<=l[i]&&r[i]<=q[j][3])
    			{
    				if(Max[i]<=2*q[j][4])
    				{
    					for(int k=q[j][4]+1;k<=Max[i];k++)
    					{
    						if(rt[k-q[j][4]]==0)
    						{
    							rt[k-q[j][4]]=rt[k];
    							rt[k]=0;
    							a[rt[k]]=k-q[j][4];
    							size[k-q[j][4]]+=size[k];
    							size[k]=0;
							}
							else
							{
								uf[rt[k]]=rt[k-q[j][4]];
								rt[k]=0;
    							size[k-q[j][4]]+=size[k];
    							size[k]=0;
							}
						}
    					Max[i]=q[j][4];
					}
					else
					{
						for(int k=0;k<=q[j][4];k++)
						{
							if(rt[k+q[j][4]]==0)
    						{
    							rt[k+q[j][4]]=rt[k];
    							rt[k]=0;
    							a[rt[k]]=k+q[j][4];
    							size[k+q[j][4]]+=size[k];
    							size[k]=0;
							}
							else
							{
								uf[rt[k]]=rt[k+q[j][4]];
								rt[k]=0;
    							size[k+q[j][4]]+=size[k];
    							size[k]=0;
							}
						}
    					Max[i]-=q[j][4];
    					lazy[i]+=q[j][4];
					}
				}
				else
				{
					for(int k=l[i];k<=r[i];k++)
					{
						a[k]=a[uf_ask(k)]-lazy[i];
					}
					lazy[i]=0;
					for(int k=max(l[i],q[j][2]);k<=min(r[i],q[j][3]);k++)
					{
						if(a[k]>q[j][4])
						{
							a[k]-=q[j][4];
						}
					}
					for(int k=0;k<=100000;k++)
    				{
			    		size[k]=0;
			    		rt[k]=0;
					}
			    	for(int k=l[i];k<=r[i];k++)
			    	{
			    		Max[i]=max(Max[i],a[k]);
			    		uf[k]=k;
			    		size[a[k]]++;
			    		if(rt[a[k]])
			    		{
			    			uf[k]=rt[a[k]];
						}
						else
						{
							rt[a[k]]=k;
						}
					}
				}
			}
			else
			{
				if(ans[j]<0)
				{
					ans[j]=0;
				}
				if(q[j][2]<=l[i]&&r[i]<=q[j][3])
    			{
    				ans[j]+=size[q[j][4]+lazy[i]];
				}
				else
				{
					for(int k=max(l[i],q[j][2]);k<=min(r[i],q[j][3]);k++)
					{
						if(a[uf_ask(k)]-lazy[i]==q[j][4])
						{
							ans[j]++;
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(ans[i]>=0)
		{
			cout<<ans[i]<<endl; 
		} 
	}
}

第三个样例错了/kk