区间数不同的数的个数是个常见的套路,不说了。

考虑这个区间修改怎么办——意味着需要修改一堆数的 $pre$。

假设对于修改前,有一段区间 $[l’,r’],l\leq l’\leq r’\leq r$ ,满足这一段区间中的数都是相同的。那么进行了修改过后,容易发现改变 $pre$ 只有 $pre_{l’},pre_{r”}$ ,这里 $pre_{r”}$ 满足修改前,$pre_{r”}=r’$ 。

接着考虑,如果最开始整个序列有 $n$ 个区间,显而易见的,如果一次修改覆盖到了 $a$ 个完整的区间并且碰到了 $b\leq 2$ 个不完整的区间,那么暴力进行修改的话是 $a+b$ 次修改的,然后区间数就会减去 $a-1$ 。

由于区间数最多减到 $1$,又因为 $b\leq 2$ ,所以其实暴力修改的次数是 $O(n+m)$ 级别的。事实上,最坏情况大概是 $n+2m$ 次修改。

所以拿一个 set 维护一下区间,然后维护 $pre$ 的话用二维线段树即可。

时间复杂度是 $O((n+m)\log n$ ?只有 $10^5$ 所以应该不会被卡常吧?


关于实现:

  • 二维线段树:最坏点得跑 $2.7s$ 。(空间 $\log^2$)
  • 树状数组 + 动态开点线段树:最坏点 $1.7s$,足以通过 loj 数据。(空间 $\log ^2$)。

  • CDQ + 平衡树:卡住了懒得调。(空间 $\log$)。

  • CDQ + 树状数组:最坏点 $0.9s$,足以通过 luogu 数据。(空间 $\log$)。

容易发现 luogu 的空间有毒,甚至不足以开下两个 Node 数组搞 CDQ,所以可以开两个 int 数组维护编号(具体见代码实现)

而且为了加速,这里采用归并排序。


关于代码。

树状数组 + 动态开点线段树:详见提交记录

CDQ + 树状数组:

const int N=1e5+5;
const int M=1e6+5;

int n,m,_,cnt,a[N],id[M],ti[M],ans[N],h[N<<1];
struct Query {int tim,l,r,val,typ,op;} q[M];

namespace ChthollyTree { // {{{ ChthollyTree
    #define ins insert

    int pre[N],las[N<<1];
    struct Node {
        int l,r,val;
        bool operator < (const Node &kls) const {return r<kls.l;}
    };
    std::set <Node> seq;
    std::set <pii> sta[N<<1];

    inline void update(int x,int now) {
        q[++cnt]=(Query){cnt,x,-1,pre[x],0,-1},
        q[++cnt]=(Query){cnt,x,-1,pre[x]=now,0,1};
    }
    inline void init() {
        lep(i,1,n) {
            a[i]=std::lower_bound(h+1,h+1+_,a[i])-h;
            q[++cnt]=(Query){cnt,i,-1,pre[i]=las[a[i]],0,1},las[a[i]]=i;
            seq.ins((Node){i,i,a[i]}),sta[a[i]].ins(mkp(i,i));
        }
        lep(i,1,_) sta[i].ins(mkp(0,0));
    }
    inline void insert(int l,int r,int val) {
        std::set <pii>::iterator it2=sta[val].upper_bound(mkp(l,r)),it1=it2; --it2;
        if(it1!=sta[val].end()) update(it1->fi,r); update(l,it2->se);
        sta[val].ins(mkp(l,r)),seq.ins((Node){l,r,val});
    }
    inline void erase(int l,int r,int val,int _flag) {
        std::set <pii>::iterator it2=sta[val].upper_bound(mkp(l,r)),it1=it2; --it2,--it2;
        if(it1!=sta[val].end()) update(it1->fi,it2->se);
        if(l!=_flag) update(l,l-1);
        sta[val].erase(mkp(l,r)),seq.erase((Node){l,r,val});
    }
    inline void cut(int l,int r,int val,int pos) {
        seq.erase((Node){l,r,val}),sta[val].erase(mkp(l,r));
        seq.ins((Node){l,pos,val}),sta[val].ins(mkp(l,pos));
        seq.ins((Node){pos+1,r,val}),sta[val].ins(mkp(pos+1,r)); 
    }
    inline void split(int L,int R,int val) {
        std::set <Node>::iterator it=seq.lower_bound((Node){L,L-1,0});

        if(it->l<=L&&R<=it->r) {
            int l=it->l,r=it->r,_val=it->val;
            if(l<L) cut(l,r,_val,L-1);
            if(R<r) cut(L,r,_val,R);
            erase(L,R,_val,L);
        } else while(it!=seq.end()&&it->l<=R) {
            int l=it->l,r=it->r,_val=it->val; ++it;
            if(L<=l&&r<=R) erase(l,r,_val,L);
            else {
                if(l<L&&L<=r&&r<=R) cut(l,r,_val,L-1),erase(L,r,_val,L);
                if(L<=l&&l<=R&&R<r) cut(l,r,_val,R),erase(l,R,_val,L);
            }
        }
        insert(L,R,val);
    }
} using namespace ChthollyTree; // }}}

// {{{ cdq divide

// {{{ BIT

int res,c[N];
inline int lowbit(int x) {return x&(-x);}
inline void modify(int x,int y) {for(;x<=n;x+=lowbit(x)) c[x]+=y;}
inline int query(int l,int r) {
    --l,res=0;
    while(r>l) res+=c[r],r-=lowbit(r);
    while(l>r) res-=c[l],l-=lowbit(l);
    return res;
}

// }}}

void cdq(int l,int r) {
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);

    int L=mid+1; lep(i,l,mid) {
        while(L<=r&&q[id[L]].val<q[id[i]].val) {
            if(q[id[L]].typ) ans[q[id[L]].typ]+=q[id[L]].op*query(q[id[L]].l,q[id[L]].r);
            ++L;
        }
        if(!q[id[i]].typ) modify(q[id[i]].l,q[id[i]].op);
    }
    while(L<=r) {
        if(q[id[L]].typ) ans[q[id[L]].typ]+=q[id[L]].op*query(q[id[L]].l,q[id[L]].r);
        ++L;
    }
    lep(i,l,mid) if(!q[id[i]].typ) modify(q[id[i]].l,-q[id[i]].op);

    int i=l,j=mid+1,t=l;
    while(i<=mid&&j<=r) ti[t++]=(q[id[i]].val<q[id[j]].val)?id[i++]:id[j++];
    while(i<=mid) ti[t++]=id[i++];
    while(j<=r) ti[t++]=id[j++];
    lep(i,l,r) id[i]=ti[i];
}
// }}}

int query_cnt,_op[N],_l[N],_r[N],_x[N];
int main() {
    IN(n,m);
    lep(i,1,n) IN(a[i]),h[++_]=a[i];
    lep(i,1,m) {
        IN(_op[i],_l[i],_r[i]);
        if(_op[i]==1) h[++_]=_x[i]=int(IN);
    }

    std::sort(h+1,h+1+_); int tmp=_; _=1;
    lep(i,2,tmp) if(h[i]!=h[_]) h[++_]=h[i];

    init();
    lep(i,1,m) {
        if(_op[i]==1) split(_l[i],_r[i],std::lower_bound(h+1,h+1+_,_x[i])-h);
        if(_op[i]==2) q[++cnt]=(Query){cnt,_l[i],_r[i],_l[i]-1,++query_cnt,1};
    }

    lep(i,1,cnt) id[i]=i;
    cdq(1,cnt);
    lep(i,1,query_cnt) printf("%d\n",ans[i]);
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

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