rt。

TLE #1 #2 #3 #11。

调块长可以把 #11 过掉，但是 #2 会 WA，其它依旧 TLE。

写法是链表。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=sqrt(N)+10; 
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	short op;
	int l,r,x;
}Q[N];
int n,m,k,t,h,op,l,r,x,Max,Tag,cnt;
int a[N],s[N],A[N],ans[N];
int L[M],R[M];
int Begin[N],End[N],siz[N],id[N],nxt[N];
inline void insert(register int x,register int y){
	if(!Begin[x]){
		id[++cnt]=x;
		Begin[x]=End[x]=y;
		siz[x]=1;
	}
	else{
		nxt[End[x]]=y;
		End[x]=y;
		++siz[x];
	}
}
inline void merge(register int x,register int y){
	if(!Begin[x]){
		id[++cnt]=x;
		Begin[x]=Begin[y];
		End[x]=End[y];
		siz[x]=siz[y];
	}
	else{
		nxt[End[x]]=Begin[y];
		End[x]=End[y];
		siz[x]+=siz[y];
	}
	Begin[y]=End[y]=siz[y]=0;
}
inline void dfs(register int rt,register int l,register int r,register int i){
	register int x=Begin[rt];
	while(1){
		if(x>=l&&x<=r)
		  ans[i]++;
		if(x==End[rt])
		  break;
		x=nxt[x];
	}
}
inline void clr(register int rt){
	register int x=Begin[rt];
	while(1){
		a[x]=rt-Tag;
		int t=nxt[x];
		nxt[x]=0;
		if(x==End[rt])
		  break;
		x=t;
	}
	Begin[rt]=End[rt]=siz[rt]=0;
}
inline void build(register int x){
	Max=Tag=cnt=0;
	for(register int i=L[x];i<=R[x];i++){
		Max=max(Max,a[i]);
		insert(a[i],i);
	}
}
inline void tidy(register int x){
	for(register int i=1;i<=cnt;i++){
		clr(id[i]);
		id[i]=0;
	}
}
inline void solve(register int x){
	for(register int i=1;i<=m;i++){
		if(Q[i].r<L[x]||Q[i].l>R[x])
		  continue;
//		cerr<<Max+Tag<<'\n';
		op=Q[i].op,l=max(L[x],Q[i].l),r=min(R[x],Q[i].r),h=Q[i].x;
		if(!h){
			ans[i]=s[Q[i].r]-s[Q[i].l-1];
			continue;
		}
		if(op==1){
			if(l==L[x]&&R[x]==r){
				if(Max<=2*h){
					for(register int j=h+Tag+1;j<=Max+Tag;j++)
					  if(Begin[j])
					    merge(j-h,j);
					Max=h;
				}
				else{
					for(register int j=Tag+1;j<=h+Tag;j++)
					  if(Begin[j])
						merge(j+h,j);
					Tag+=h;
					Max-=h;
				}
			}
			else{
				tidy(x);
				for(register int j=l;j<=r;j++)
				  if(a[j]>h)
				    a[j]-=h;
				build(x);
			}
		}
		else{
			if(l==L[x]&&R[x]==r)
			  ans[i]+=siz[h+Tag];
			else
			  dfs(h+Tag,l,r,i);
		}
	}
}
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	n=read(),m=read();
	k=1200,t=(n+k-1)/k;
	for(register int i=1;i<=t;i++){
		L[i]=(i-1)*k+1;
		R[i]=i*k;
	}
	R[t]=n;
	for(register int i=1;i<=n;i++){
		a[i]=read();
		A[i]=(i-1)/k+1;
		s[i]=s[i-1]+(a[i]==0);
	}
	for(register int i=1;i<=m;i++)
	  Q[i]={(short)read(),read(),read(),read()};
	for(register int i=1;i<=t;i++){
		build(i);
		solve(i);
		tidy(i);
//		cerr<<i<<'\n';
	}
	for(register int i=1;i<=m;i++){
		if(Q[i].op==2){
			write(ans[i]);
			putchar('\n');
		}
	}
	return 0;
}