第二分块30pt TLE求调

// Problem: P4117 [Ynoi2018] 五彩斑斓的世界
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4117
// Memory Limit: 64 MB
// Time Limit: 7500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define N 100010
#define M 1000010
using namespace std;
int n,m,qlen,a[M];
inline int read() {
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return f*res;
}
struct query{
	int opt,l,r,x;
}q[M];
int ql[N],qr[N],qn,tag,mx;
int fa[M],ans[M],rt[N],siz[N],mp[M];
inline int find(int x) {
	while(x!=fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
inline void build(int l,int r) {
	mx=-1,tag=0;
	memset(rt,0,sizeof(rt));
	memset(siz,0,sizeof(siz));
	for(int i=l; i<=r; i++) {
		mx=max(mx,a[i]);
		if(rt[a[i]]) fa[i]=rt[a[i]];
		else {
			rt[a[i]]=fa[i]=i;
			mp[i]=a[i];
		} siz[a[i]]++;
	}
}
inline void merge(int x,int y) {
	if(rt[y]) fa[rt[x]]=rt[y];
	else rt[y]=rt[x],mp[rt[y]]=y;
	siz[y]+=siz[x],rt[x]=siz[x]=0;
}
inline void update(int x) {
	if(x > (mx - tag) / 2){
		for(int i = x + 1 + tag;i <= mx;i ++)if(rt[i]) merge(i,i - x);
		mx = min(mx,x + tag);
	}
	else {
		for(int i = tag; i <= x + tag;i ++)if(rt[i])merge(i,i + x);
		tag += x;
	}
}
inline void rebuild(int l,int r,int id) {
	for(int i=l; i<=r; i++) {
		a[i]=mp[find(i)];
		rt[a[i]]=siz[a[i]]=0;
		a[i]-=tag;
	}
	for(int i=l; i<=r; i++) mp[i]=0;
	for(int i=max(q[id].l,l); i<=min(q[id].r,r); i++) if(a[i]>q[id].x) a[i]-=q[id].x;
	build(l,r);
}
inline int ask(int l,int r,int id) {
	int res=0;
    for(int i=max(l,q[id].l); i<=min(r,q[id].r); i++) if(mp[find(i)]-tag==q[id].x) res++;
    return res;
}
inline void write(int x){
    if(x < 0)putchar('-'),x = -x;
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
	n=read(),m=read(),qlen=sqrt(n);
	memset(ql,0x3f,sizeof(ql));
	for(int i=1; i<=n; i++) a[i]=read();
	for(int i=1; i<=m; i++) q[i]=query{read(),read(),read(),read()};
	for(int i=1; i<=n; i++) 
	    ql[(i-1)/qlen+1]=min(ql[(i-1)/qlen+1],i),
		qr[(i-1)/qlen+1]=max(qr[(i-1)/qlen+1],i);
	qn=(n-1)/qlen+1;
	printf("%d\n",qn);
	for(int kkk=1; kkk<=qn; kkk++) {
//		printf("%d %d\n",ql[kkk],qr[kkk]);
		int l=ql[kkk],r=qr[kkk];
		tag=0,mx=-1,build(l,r);
		for(int i=1; i<=m; i++) {
			if(r<q[i].l||q[i].r<l) continue;
			if(q[i].opt==1) {
				if(q[i].l<=l&&r<=q[i].r) update(q[i].x);
			    else rebuild(l,r,i);
			} else {
				if(tag+q[i].x>1e5+1) continue;
				if(q[i].l<=l&&r<=q[i].r) ans[i]+=siz[tag+q[i].x];
				else ans[i]+=ask(l,r,i);
			}
		}
	}
	for(int i=1; i<=m; i++) if(q[i].opt==2) write(ans[i]),puts("");
	return 0;
}