Luogu

分析

考虑分块。

对于每一块，维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的，因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式

• 如果 $2x\geq mx$，则直接将所有 $>x$ 的数减去 $mx$。这样子是 $\mathcal{O}(x)$ 的。
• 否则，将所有 $\leq x$ 的数加上 $x$，然后打一个减法标记。这样子也是 $\mathcal{O}(x)$ 的。

然后对每块开一个并查集维护相同的数构成的连通块。这样子修改时做 $\mathcal{O}(x)$ 次合并即可。

然后我们需要维护的是每个数的出现次数，在合并时维护即可。

但是这样子空间是 $\mathcal{O}(n\sqrt{n})$ 的，而空间限制只有 62.5MB，显然是开不下的。

可以逐块处理，即对每一块依次计算它对每个询问的答案的贡献。这样子空间就可以降为 $\mathcal{O}(n)$ 了。

具体实现和细节可以参考代码。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
typedef long long ll;

namespace io {
    const int SIZE=1<<21;
    char ibuf[SIZE|1],*iS,*iT,obuf[SIZE|1],*oS=obuf,*oT=obuf+SIZE-1;
    void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; }
    char getc() {
        if (iS==iT) {
            iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin);
            if (iS==iT) return EOF;
        }
        return *iS++;
    }
    void putc(char c) { *oS++=c; if (oS==oT) flush(); }
    int read() {
        int X=0; char c=getc();
        while (c<'0'||c>'9') c=getc();
        while (c>='0'&&c<='9') X=X*10+c-'0',c=getc();
        return X;
    }
    void write(int x) {
        if (!x) { putc('0'); return; }
        if (x<0) putc('-'),x=-x;
        static int s[30]; int top=0;
        while (x) s[++top]=x%10,x/=10;
        while (top) putc(s[top--]+'0');
    }
    struct flusher { ~flusher() { flush(); } } io_flusher;
}
using io::putc;
using io::read;
using io::write;

const int N=500000+10;

int n,m,B,a[N],ans[N];
struct Q { int op,l,r,x; } q[N];

int f[N],rt[N],cnt[N],val[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void merge(int x,int y) {
    if (rt[y]) f[rt[x]]=rt[y];
    else rt[y]=rt[x],val[rt[y]]=y;
    cnt[y]+=cnt[x],rt[x]=cnt[x]=0;
}

int mx,tag;
void build(int l,int r) {
    mx=tag=0; memset(cnt,0,sizeof(cnt)),memset(rt,0,sizeof(rt));
    for (int i=l;i<=r;++i) {
        mx=max(mx,a[i]);
        if (rt[a[i]]) f[i]=rt[a[i]];
        else rt[a[i]]=f[i]=i,val[i]=a[i];
        ++cnt[a[i]];
    }
}
void modify(int l,int r,int x) {
    if ((x<<1)>mx-tag) {
        for (int i=mx-tag;i>x;--i)
            if (rt[i+tag]) merge(i+tag,i-x+tag);
        if (x<mx-tag) mx=x+tag;
    } else {
        for (int i=1;i<=x;++i)
            if (rt[i+tag]) merge(i+tag,i+x+tag);
        tag+=x;
    }
}
void rebuild(int l,int r,int ql,int qr,int x) {
    for (int i=l;i<=r;++i)
        a[i]=val[find(i)]-tag,rt[a[i]+tag]=cnt[a[i]+tag]=0;
    for (int i=l;i<=r;++i) val[i]=0;
    mx=tag=0;
    for (int i=max(l,ql);i<=min(r,qr);++i) if (a[i]>x) a[i]-=x;
    for (int i=l;i<=r;++i) {
        mx=max(mx,a[i]);
        if (rt[a[i]]) f[i]=rt[a[i]];
        else rt[a[i]]=f[i]=i,val[i]=a[i];
        ++cnt[a[i]];
    }
}
int query(int l,int r,int ql,int qr,int x) {
    if (ql<=l&&r<=qr) return cnt[x+tag];
    int res=0;
    for (int i=max(l,ql);i<=min(r,qr);++i)
        if (val[find(i)]-tag==x) ++res;
    return res;
}

int main() {
    n=read(),m=read(); B=sqrt(n); int cnt=(n-1)/B+1;
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=m;++i) q[i]=(Q){read(),read(),read(),read()};
    for (int i=1;i<=cnt;++i) {
        int L=(i-1)*B+1,R=min(i*B,n);
        build(L,R);
        for (int j=1;j<=m;++j) {
            if (q[j].r<L||R<q[j].l) continue;
            if (q[j].op==2) ans[j]+=query(L,R,q[j].l,q[j].r,q[j].x);
            else {
                if (q[j].l<=L&&R<=q[j].r) modify(L,R,q[j].x);
                else rebuild(L,R,q[j].l,q[j].r,q[j].x);
            }
        }
    }
    for (int i=1;i<=m;++i) if (q[i].op==2) printf("%d\n",ans[i]);
    return 0;
}