一开始是 WA on #11，然后把数组大小全都 +5 就成了 WA on #9，再把数组全都开到几百万就 WA on #9,#14。

不知道是什么神秘的 UB，有没有大佬帮忙找一下啊/kk

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
using namespace std;
template<typename T> void Read(T &x)
{
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
}
int n,Q,m,op,l,r,k,rt,tot=0,ch[1000001][2],siz[1000001],rnd[1000001],t[1000001],b[1000001];
struct sz{int ind,v;}a[1000001],val[1000001];
bool cmp(sz a1,sz a2){return a1.v<a2.v;}
int lowbit(int x){return x&(-x);}
int query(int now){int res=0;for(int i=now;i;i-=lowbit(i))res+=t[i];return res;}
void modify(int now,int z){for(int i=now;i<=n;i+=lowbit(i))t[i]+=z;}
void pushup(int now){siz[now]=siz[ch[now][0]]+siz[ch[now][1]]+1;}
int newnode(sz a1)
{
	tot++;
	siz[tot]=1;
	ch[tot][0]=ch[tot][1]=0;
	rnd[tot]=rand();
	val[tot]=a1;
	return tot;
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(rnd[x]<rnd[y])
	{
		ch[x][1]=merge(ch[x][1],y);
		pushup(x);
		return x;
	}
	else
	{
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void split(int now,int k,int &x,int &y)
{
	if(!now){x=y=0;return;}
	if(val[now].v<=k)
	{
		x=now;
		split(ch[now][1],k,ch[now][1],y);
	}
	else
	{
		y=now;
		split(ch[now][0],k,x,ch[now][0]);
	}
	pushup(now);
}
void del(int now)
{
	if(!now) return;
	modify(val[now].ind,1);
	del(ch[now][0]);del(ch[now][1]);
}
int build(int tl,int tr)
{
	if(tl==tr) return newnode(a[tl]);
	int mid=(tl+tr)/2;
	return merge(build(tl,mid),build(mid+1,tr));
}

int kc1,kc2,ks,Op[300005],bl[300005],L[601],R[601],ans[300005];
struct query
{
	int op,l,r,k,bh;
	friend bool operator <(const query &a1,const query &a2){return a1.k==a2.k?a1.bh<a2.bh:a1.k<a2.k;}
} q[300005];
int s1[300005],s2[300005],anc[300005];
int Find(int x){return anc[x]==x?x:anc[x]=Find(anc[x]);}
void add1(int x){s1[x]++;s2[bl[x]]++;}
int ask1(int l,int r)
{
	int pl=bl[l],pr=bl[r],res=0;
	if(pl==pr)
	{
		for(int i=l;i<=r;i++) res+=s1[i];
		return res;
	}
	for(int i=l;i<=R[pl];i++) res+=s1[i];
	for(int i=L[pr];i<=r;i++) res+=s1[i];
	for(int i=pl+1;i<=pr-1;i++) res+=s2[i];
	return res;
}
void sol1(int l,int r)
{
	for(int i=1;i<=n+1;i++) anc[i]=i;
	memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));
	for(int i=l;i<=r;i++)
	{
		if(q[i].op==1)
		{
			int ll=lower_bound(b+1,b+1+n,q[i].l)-b,rr=upper_bound(b+1,b+1+n,q[i].r)-b-1;
			int be=Find(ll);
			while(be<=rr) add1(a[be].ind),anc[be]=anc[be+1],be=Find(be+1);
		}
		else ans[q[i].bh]=ask1(q[i].l,q[i].r);
	}
}

struct node
{
	int l,r,bh;
	node(int ll=0,int rr=0,int bhh=0){l=ll;r=rr;bh=bhh;}
	friend bool operator <(const node &a1,const node &a2){return a1.l<a2.l;}
} st[300005];
struct edge
{
	int nxt,op,l,r;
	edge(int nxtt=0,int opp=0,int ll=0,int rr=0){nxt=nxtt;op=opp;l=ll;r=rr;}
} e[1200005];
int cnt=0,top=0,h[300005],S1[300005],S2[300005];
set<node> s;
typedef set<node>::iterator iter;
void insedge(int x,int op,int l,int r){e[++cnt]=edge(h[x],op,l,r);h[x]=cnt;}
void add2(int x)
{
	for(int i=x;i<=R[bl[x]];i++) S1[i]++;
	for(int i=bl[x]+1;i<=ks;i++) S2[i]++;
}
int ask2(int x){if(!x) return 0;return S1[x]+S2[bl[x]];}
void inscz(int l,int r,int t){st[++top]=node(l,r,t);}
void ers(int l,int r,int t)
{
	for(int i=1;i<=top;i++)
		if(st[i].l==l&&st[i].r==r)
		{
			insedge(r,1,st[i].bh,t);insedge(l-1,-1,st[i].bh,t);
			for(int j=i;j<top;j++) st[j]=st[j+1];top--;
			return;
		}
}
void sol2(int ll,int rr)
{
	s.clear();top=0;
	iter il,ir;
	for(int i=ll;i<=rr;i++)
		if(q[i].op==1)
		{
			int l=lower_bound(b+1,b+1+n,q[i].l)-b,r=upper_bound(b+1,b+1+n,q[i].r)-b-1;
			if(l>r) continue;
			if(s.empty()) goto eeeen;
			il=s.lower_bound(node(l,0,0)),ir=s.upper_bound(node(r,0,0));
			if(il!=s.begin())
			{
				iter tmp=il;tmp--;
				if(tmp->r>=l) il--;
			}
			if(ir==s.begin()||(ir!=s.begin()&&(--ir)->r<l)) goto eeeen;
			l=min(l,il->l),r=max(r,ir->r);
			while(il!=ir) ers(il->l,il->r,i),il=s.erase(il);
			ers(ir->l,ir->r,i);s.erase(ir);
			eeeen:
			inscz(l,r,i);s.insert(node(l,r,i));
		}
	for(int i=1;i<=top;i++)
		insedge(st[i].r,1,st[i].bh,rr),insedge(st[i].l-1,-1,st[i].bh,rr),st[i].l=st[i].r=st[i].bh=0;
}
void sol()
{
	for(int i=1;i<=n;i++)
	{
		add2(a[i].ind);
		for(int j=h[i];j;j=e[j].nxt)
			for(int k=e[j].l;k<=e[j].r;k++)
				if(q[k].op==2) ans[q[k].bh]+=e[j].op*(ask2(q[k].r)-ask2(q[k].l-1));
	}
}
int main()
{
	Read(n);Read(Q);Read(m);
	for(int i=1;i<=n;i++)
	{
		Read(a[i].v);b[i]=a[i].v;
		a[i].ind=i;
	}
	sort(a+1,a+1+n,cmp);sort(b+1,b+1+n);
	if(m==1)
	{
	
	for(int i=1;i<=n;i++) rt=merge(rt,newnode(a[i]));
	while(Q--)
	{
		Read(op);Read(l);Read(r);Read(k);
		if(op==1)
		{
			int x,y,z;
			split(rt,l-1,x,y);
			split(y,r,y,z);
			del(y);
			rt=merge(x,z);
		}
		if(op==2) printf("%d\n",query(r)-query(l-1));
	}
	
	}
	else
	{
	
	kc1=sqrt(n);kc2=sqrt(Q);ks=(n+kc1-1)/kc1;
	for(int i=1;i<=n;i++) bl[i]=(i-1)/kc1+1;ks=bl[n];
	for(int i=1;i<=ks;i++) L[i]=(i-1)*kc1+1,R[i]=min(i*kc1,n);
	for(int i=1;i<=Q;i++) Read(q[i].op),Read(q[i].l),Read(q[i].r),Read(q[i].k),q[i].bh=i,Op[i]=q[i].op;
	sort(q+1,q+1+Q);
	for(int l=1,r;r<=Q;l=r+1)
	{
		r=l;
		while(q[r+1].k==q[l].k) r++;
		if(r-l+1>=kc2) sol1(l,r);
		else sol2(l,r);
	}
	sol();
	for(int i=1;i<=Q;i++)
		if(Op[i]==2) printf("%d\n",ans[i]);
	
	}
	return 0;
}