首先考虑一个全局的做法。

对于这个 $1$ 号操作,我们有两种方式做:

  • 将所有 $\leq x$ 的数加上 $x$,然后全局打上一个减法标记。
  • 将所有 $>x$ 的数减去 $x$ 。

如果当前全局最大值是 $lim$ ,那么第一种方式相当于用 $x$ 次修改将 $lim$ 减去 $x$ ,第二种方式相当于用 $lim-x$ 次修改将 $lim$ 减去 $x$ 。

因为值域只有 $S=10^5$ 级别,考虑一个修改次数也是 $O(S)$ 级别的做法。

容易发现两种方式各有优劣:第一种方式如果一直无脑加的话,容易发现,当 $x>\frac{lim}{2}$ 的时候,就不容易确定上界的位置了,可以用一种很轻松的方法将其卡掉:首先只有 $[1,10^5]$ ,然后第一次操作 $x=10^5$ ,容易发现操作完了后 $lim=10^5$ ,接下来由于没有 $lim$ 的控制,一些 $x>1$ 的操作都会直接枚举到 $x$(这显然是浪费次数的)。

但是如果 $x\leq \frac{lim}{2}$ ,就可以放心减,因为这个时候 $lim$ 减去 $x$ 后还是最大值。

那么对于 $x>\frac{lim}{2}$ 的部分怎么做呢?这个时候可以考虑用第二种方法,然后将 $lim$ 定为 $x$ 。这个时候简单计算一下可以发现没有多余操作了。

接下来就是维护颜色块,考虑用并查集维护,这样十分方便合并。

拓展到区间的做法,将序列分块,每个块用一个并查集然后照做就是了。但是这样空间开不下,所以要离线,然后一个一个块的处理贡献。

  • 整块修改:按照上面的做法即可,修改权值相当于合并并查集。
  • 散块修改:重构并查集,重构的复杂度是 $O(\sqrt{n})$ 的,是正确的。
  • 整块查询:直接查询对应并查集的大小即可。
  • 散块查询:暴力枚举这些位置,然后找到它们归属的并查集的数是否等于 $x$ 即可。

代码细节较多,长度较短,本题不卡常,注意实现即可。

因为常数原因,稍微调了一下块大小;并查集合并可以用启发式合并,不过重构比较频繁所以可能作用不大;注意预处理的时候没必要求出每个块的 $l,r$ ,而是用的时候再求,否则调用这么多次 L[t],R[t] 其实是十分慢的(修正前 $65\ pts$,修正后 $100\ pts$)。

const int N=1e6+5;
const int M=5e5+5;
const int SqrtN=3e3+5;

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

// {{{ Block

int rt[N],fa[N],siz[N],col[N];
inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

/*--------------------------------------------------*/

int sqrtn,tag,lim,id[N],L,R;

inline void init() {
    sqrtn=sqrt(n*7/10+1);
    lep(i,1,n) id[i]=(i-1)/sqrtn+1;
}

inline void merge(int a,int b) {
    if(!rt[b]) rt[b]=rt[a];
    else {
        if(siz[rt[a]]>siz[rt[b]]) swap(rt[a],rt[b]);
        fa[rt[a]]=rt[b],siz[rt[b]]+=siz[rt[a]],col[rt[a]]=siz[rt[a]]=0;
    }
    col[rt[b]]=b,rt[a]=0;
}
inline void modify(const int &t,int x) {
    if(x>lim) return ;
    if(x<=lim/2) {rep(i,x,0) merge(i+tag,i+x+tag); tag+=x,lim-=x;}
    else {lep(i,x+1,lim) merge(i+tag,i+tag-x); lim=x;}
}

// {{{ solve

inline void get_dsu(const int &t) {
    lep(i,L,R) {
        if(!rt[a[i]]) col[rt[a[i]]=i]=a[i],siz[i]=0;
        ++siz[fa[i]=rt[a[i]]],chkmax(lim,a[i]);
    }
}
inline void rebuild(const int &t,int l,int r,int x) {
    lep(i,L,R) rt[a[i]=col[find(i)]]=siz[i]=0,a[i]-=tag;
    lep(i,max(l,L),min(r,R)) if(a[i]>x) a[i]-=x;
    get_dsu(t),tag=0;
}

inline void solve(const int &t) {
    CLEAR(rt),lim=tag=0;
    lep(i,L,R) siz[i]=col[i]=0; get_dsu(t);

    lep(_,1,m) {
        if(q[_].r<L||q[_].l>R) continue;
        if(q[_].op==1) {
            if(q[_].l<=L&&R<=q[_].r) modify(t,q[_].x);
            else rebuild(t,q[_].l,q[_].r,q[_].x);
        } else {
            if(!rt[q[_].x+tag]) continue;

            if(q[_].l<=L&&R<=q[_].r) ans[q[_].id]+=siz[rt[q[_].x+tag]];
            else {
                const int _l=max(L,q[_].l),_r=min(R,q[_].r);
                lep(i,_l,_r) ans[q[_].id]+=(col[find(i)]==q[_].x+tag);
            }
        }
    }
}

// }}}

// }}}

int query_cnt;
int main() {
    IN(n,m);
    lep(i,1,n) IN(a[i]);
    init();

    lep(i,1,m) {
        IN(q[i].op,q[i].l,q[i].r,q[i].x);
        if(q[i].op==2) q[i].id=++query_cnt;
    }

    lep(i,1,id[n]) L=(i-1)*sqrtn+1,R=min(L+sqrtn-1,n),solve(i);
    lep(i,1,query_cnt) printf("%d\n",ans[i]);
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code