写了两天多... 主要是中间两个晚上都在搞别的事情.

五 彩 斑 斓 的 世 界 (指 TLE,RE,MLE,AC 和 WA).

解题思路

首先看到 Ynoi 显然毫无疑问就是

然后考虑怎么分.看到值域 $5\cdot10^5$ 想到值域分块 这道题并不需要值域分块. 但是这么小 (?) 的值域还是有一定的提示, 只不过最后的解法还是很接近魔法就是了.

更新 (操作 $1$)

可以看到 $a$ 只会减小, 总共有 $\sqrt n$ 个块, 如果每个块的总复杂度在 $\Theta(n\lg n)$(值域同阶)就可以接受. 考虑每一次的修改操作

• 如果 $x$ 很大, 那么要减的部分就很少, 可以暴力去做.
• 如果 $x$ 很小, 那么将所有小于等于 $x$ 的加上一个 $x$, 再打上整体减 $x$ 的标记; 而这样的也很少, 看起来也可以暴力.

更具体地, 我们以 $2x$ 作为分界线. 记 $m=\max\{a_{i\in 当前块}\}$, 当 $2x>m$ 时将所有大于 $x$ 的减去 $x$, 否则所有小于 $x$ 的加上 $x$ 再打标记. 假设对于相同大小的 $a_i$ 操作一次总时间是 $t$, 这样做我们要么用 $\Theta(t(m-x))$ 将 $m$ 缩小到 $x$, 即缩小了 $m-x$; 要么用 $\Theta(tx)$ 的时间将 $m$ 缩小了 $x$(因为小于 $x$ 的都被处理掉了), 所以总复杂度是 $\Theta(t\max a)=\Theta(tn)$. 如果 $t$ 够小看起来就能过了.

仔细观察, 发现这个操作类似于合并两个数, 想到 [Ynoi2018] 未来日记 ], 类似地使用并查集, 此时 $t=\lg n$, 单块总复杂度 $\Theta(n\lg n)$, 满足了要求.

以上是对于整块的部分, 对于散块就直接拆了重构. 容易证明最多只会有 $2n$ 个散块 (每次操作最多出现两个散块), 对于散块总复杂度是 $\Theta(n\sqrt n)$, 和整块加在一起修改的总复杂度就是 $\Theta(n\sqrt n\lg n)$.

查询 (操作 $2$)

查询看起来就比较好办了. 整块并查集维护 $size$, 散块暴力即可 (和更新类似, 最多只会有 $2n$ 个散块). 总复杂度 $\Theta(n\sqrt n)$.

MLE?

这道题卡空间, 开不下 $\Theta(n\sqrt n)$, 所以必须要每个块离线下来单独处理. 询问在块与块之间是独立的, 所以没有什么大问题.

复杂度分析

更新是 $\Theta (n\sqrt n\lg n)$, 查询是 $\Theta(n\sqrt n)$, 加起来就是 $\Theta(n\sqrt n\lg n)$.

当然这是 Ynoi, 所以自然要调块长. 实测块长在 $1000$ 的时候能过完, 总共有 $500$ 个块.

值得注意的地方

嗯对就是它们卡了窝一整页提交记录.

并查集要写非递归

如上所述, 这道题卡空间. 并查集递归会爆空间 (爆栈), 因为总空间(加上栈) 只有 $62.5\mathrm{MB}$.

下标与标记

记得每个数组的下标是处理标记之前的还是之后的. 这个点只能这么说, 毕竟每个人写法都不同嘛 (笑).

数组空间

某几个数组下标是处理标记之前的, 这样下标最大可以达到 $2n$(好吧其实达不到, 但是比 $n$ 要大), 所以某些数组记得开两倍空间.

双倍快乐

CF896E Welcome home, Chtholly, 直接同一份代码就行.

Code

还是没有注释.

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048577,stdin),p0==p1)?EOF:*p0++)

inline int read() {
    static char buf[1048577],*p0,*p1;
    int re=0; char ch=gc();
    while (ch<48||ch>57) ch=gc();
    while (ch>47&&ch<58) {
        re=(re<<3)+(re<<1)+(ch^48);
        ch=gc();
    }
    return re;
}

const int qa=1000,qb=500;

int a[500005],p[500005];
int nl,nr,ni,tg,mx[505];
int fat[500005],fir[1000005],siz[1000005];

inline int find_fat(int ops) {
    int np=ops,nq;
    while (np!=fat[np]) np=fat[np];
    while (ops!=np) {
        nq=fat[ops]; fat[ops]=np; ops=nq;
    }
    return np;
}

inline void init() {
    tg=0;
    memset(fir,0xff,sizeof(fir));
    memset(siz,0x00,sizeof(siz));
    for (int i=nl;i<=nr;++i) {
        if (fir[a[i]]==-1) fir[a[i]]=fat[i]=i;
        else fat[i]=fir[a[i]]; ++siz[a[i]];
    }
}

inline void update(int opl,int opr,int opx) {
    if (nl>opr||nr<opl||opx>mx[ni]) return;
    else if (nl<opl||nr>opr) {
        for (int i=nl;i<=nr;++i) {
            siz[a[i]]=0; fir[a[i]]=-1;
            a[i]=a[find_fat(i)];
        }
        for (int i=nl;i<=nr;++i) {
            a[i]-=tg;
            if (i>=opl&&i<=opr&&a[i]>opx) a[i]-=opx;
            if (fir[a[i]]==-1) fir[a[i]]=fat[i]=i;
            else fat[i]=fir[a[i]]; ++siz[a[i]];
        }
        tg=0;
    }
    else {
        if (mx[ni]<(opx<<1)) {
            for (int i=opx+tg+1;i<=mx[ni]+tg;++i) if (fir[i]!=-1) {
                if (fir[i-opx]!=-1) fat[fir[i]]=fir[i-opx];
                else a[fir[i-opx]=fir[i]]=i-opx;
                fir[i]=-1; siz[i-opx]+=siz[i]; siz[i]=0;
            }
            mx[ni]=min(mx[ni],opx);
        }
        else {
            for (int i=tg+1;i<=opx+tg;++i) if (fir[i]!=-1) {
                if (fir[i+opx]!=-1) fat[fir[i]]=fir[i+opx];
                else a[fir[i+opx]=fir[i]]=i+opx;
                fir[i]=-1; siz[i+opx]+=siz[i]; siz[i]=0;
            }
            mx[ni]-=opx; tg+=opx;
        }
    }
}

inline int count(int opl,int opr,int opx) {
    if (nl>opr||nr<opl||opx>mx[ni]) return 0;
    int r=0; opx+=tg;
    if (nl<opl||nr>opr) {
        opl=max(opl,nl); opr=min(opr,nr);
        for (int i=opl;i<=opr;++i)
            r+=a[find_fat(i)]==opx?1:0;
        return r;
    }
    else return siz[opx];
}

int main() {
    static int ql[500005],qr[500005],qx[500005],qp[500005];
    static bool qt[500005];
    int n,m; n=read(); m=read();
    for (int i=0;i<n;++i) {
        p[i]=i/qa;
        mx[p[i]]=max(mx[p[i]],a[i]=read());
    }
    for (int i=0;i<m;++i) {
        qt[i]=read()==1; ql[i]=read()-1;
        qr[i]=read()-1; qx[i]=read();
    }
    for (;ni<qb;++ni) {
        nl=ni*qa; nr=(ni+1)*qa-1; init();
        for (int j=0;j<m;++j) {
            if (qt[j]) update(ql[j],qr[j],qx[j]);
            else qp[j]+=count(ql[j],qr[j],qx[j]);
        }
    }
    for (int i=0;i<m;++i) if (!qt[i]) printf("%d\n",qp[i]);
    return 0;
}