P10516 数据结构 题解

· · 题解

给一个不带 \log 的做法。

分析

用 V 表示值域大小

首先易知 1 操作造成的单点修改总次数是 O((n+m)\sqrt V) 的，本题的其他题解也有说。

换句话说我们可以用 O((n+m)\sqrt V) 次 2 操作来完成所有 1 操作。

问题在于怎样找到需要进行的操作，以及如何进行操作。

实现

我们审视一下 1 操作：

修改所有下标在 l 到 r 之间 以及 a,b 乘积在 0 到 k 之间的点

也就是说这是一个二维的限制。

直接分块的话光维护第一维限制就需要在 O(\sqrt n) 个整块里分别操作，每个块就只剩 O(1) 的操作空间了。

因此考虑在分块的基础上再次分块。

首先，将整个序列分为 O(\sqrt n) 个小块，每个块长 O(\sqrt n) 。

然后，相邻的 O(n^{\frac 1 4}) 个小块拼成一个大块，每个大块长 O(n^{\frac 3 4})。

这样，我们就将 1 操作涉及的区间分成了 O(n^{\frac 1 4}) 个大块、 O(n^{\frac 1 4}) 个小块和 O(\sqrt n) 个单点。

这样，维护第一维就只需要处理好 O(n^{\frac 1 4}) 个整块（毕竟大块和小块的维护方式是一样的）。

维护整块内值域用类似的方法，对值域分三次块，分别是 O(V^{\frac 1 4}) 个长 O(V^{\frac 3 4}) 的块，O(\sqrt V) 个长 O(\sqrt V) 的块，O(V^{\frac 3 4}) 个长 O(V^{\frac 1 4}) 的块，每个块和每个单点都开一个链表存所有乘积在这个块内的下标。

这样我们查找整块内所有乘积在 0 到 k 之间的点就只需要 O(V^{\frac 1 4}) 的时间了。

最终时间复杂度 O((n+m)\sqrt V + m (nV)^{\frac 1 4} )

然而空间复杂度是 O(m (nV)^{\frac 1 4} ) ，还有 8 倍常数，直接炸了。

然而可以离线下来，每次只维护序列上一个大块，空间复杂度 O(m V^{\frac 1 4} ) 。

代码：

#include <cstdio>
inline int rd(){
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();
    return x;
}
const int mx=100000,blen=5000,slen=500,klen=18;
const int klen_2=klen*klen,klen_3=klen*klen*klen;
int n,m,a[100010],b[100010],l[100010],r[100010],k[100010],t[100010];
struct node{
    int pre,nxt;
    inline void init(const int at){pre=nxt=at;}
}dt[5600000];
int tot,que[100010],sz;
struct line{
    node *l;
    inline void init(const int len){
        l=dt+tot,tot+=len;
        for(int i=1;i<=len;++i)l[i].init(i);
    }
    inline void link(const int u,const int v){
        l[u].nxt=v,l[v].pre=u;
    }
    inline void add(const int u,const int to){
        link(u,l[to+n+1].nxt),link(to+n+1,u);
    }
    inline void dlt(const int p){
        l[l[p].nxt].pre=l[p].pre;
        l[l[p].pre].nxt=l[p].nxt;
        l[p].pre=l[p].nxt=p;
    }
    inline void pick(int plc)const{
        plc+=n+1;
        for(int u=l[plc].nxt;u!=plc;u=l[u].nxt)
            que[++sz]=u;
    }
};
typedef long long ll;
struct block{
    line s[4];
    ll sum;
    inline void init(){
        sum=0;
        s[0].init((mx+1)<<1);
        s[1].init(mx+1+klen_3);
        s[2].init(mx+1+klen_2);
        s[3].init(mx+1+klen);
    }
    inline void add(const int p,const ll to){
        sum+=a[p]+b[p];
        if(to>mx)return;
        s[0].add(p,to);
        if(to){
            s[1].add(p,(to+klen-1)/klen);
            s[2].add(p,(to+klen_2-1)/klen_2);
            s[3].add(p,(to+klen_3-1)/klen_3);
        }
    }
    inline void dlt(const int p){
        sum-=a[p]+b[p];
        s[0].dlt(p),s[1].dlt(p),s[2].dlt(p),s[3].dlt(p);
    }
    inline void sele(int k)const{
        s[0].pick(0);
        int nw=klen_3;
        for(int i=1;nw<=k;nw+=klen_3,++i)s[3].pick(i);
        nw+=klen_2-klen_3;
        for(int i=nw/klen_2;nw<=k;nw+=klen_2,++i)s[2].pick(i);
        nw+=klen-klen_2;
        for(int i=nw/klen;nw<=k;nw+=klen,++i)s[1].pick(i);
        for(nw+=1-klen;nw<=k;++nw)s[0].pick(nw);
    }
}blk[11];
ll ans[100010];
inline void add(const int p){
    ll v=(ll)a[p]*b[p];
    blk[0].add(p,v);
    blk[((p-1)%blen)/slen+1].add(p,v);
}
inline void dlt(const int p){
    blk[0].dlt(p);
    blk[((p-1)%blen)/slen+1].dlt(p);
}
inline void chg(const int p,const int x,const int y){
    dlt(p),a[p]=x,b[p]=y,add(p);
}
inline void adv(const int p,const int v){chg(p,a[p]+v,b[p]+v);}
inline void sol(const int at){
    const int vt=t[at];
    if(!vt)return;
    blk[0].sele(k[at]);
    for(int i=1;i<=sz;++i)
        adv(que[i],vt);
    sz=0;
}
inline bool chkq(const int p){return r[p] && k[p]==0 && t[p]==0;}
inline void pros(const int p,const int at,const int tp){
    if(tp){ans[at]+=a[p]+b[p];return;}
    ll v=(ll)a[p]*b[p];
    if(v<=k[at])adv(p,t[at]);
}
inline void part(const int l,const int r,const int at){
    if(t[at]==0 && k[at])return;
    int tl=(l-1)%blen/slen+1,tr=(r-1)%blen/slen+1,bg=l-l%blen,tp=chkq(at);
    if(tl==tr){
        for(int i=l;i<=r;++i)pros(i,at,tp);
        return;
    }
    int el=bg+tl*slen,br=bg+(tr-1)*slen+1;
    for(int i=l;i<=el;++i)pros(i,at,tp);
    for(int i=br;i<=r;++i)pros(i,at,tp);
    for(int i=tl+1;i<tr;++i){
        if(tp)ans[at]+=blk[i].sum;
        else blk[i].sele(k[at]);
    }
    if(tp)return;
    for(int i=1;i<=sz;++i)
        adv(que[i],t[at]);
    sz=0;
}
inline void file(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
}
int main(){
//  file();
    n=rd(),m=rd();
    for(int i=1;i<=n;++i)a[i]=rd();
    for(int i=1;i<=n;++i)b[i]=rd();
    for(int i=1,tp;i<=m;++i){
        tp=rd();
        if(tp==2)l[i]=rd(),k[i]=rd(),t[i]=rd();
        else if(tp==3)l[i]=rd(),r[i]=rd();
        else{
            l[i]=rd(),r[i]=rd(),k[i]=rd(),t[i]=rd();
            if(chkq(i))k[i]=1;
        }
    }
    for(int bg=1,ed;bg<=n;bg+=blen){
        ed=(bg+blen>n?n:bg+blen-1);
        tot=0;
        blk[0].init();
        for(int kb=bg,ke,at=1;kb<=ed;kb+=slen,++at){
            ke=(kb+slen>ed?ed:kb+slen-1);
            blk[at].init();
            for(int i=kb;i<=ke;++i)add(i);
        }
        for(int i=1;i<=m;++i){
            if(!r[i]){
                const int p=l[i];
                if(p<bg || p>ed)continue;
                chg(p,k[i],t[i]);
            }
            else{
                if(l[i]>ed || r[i]<bg)continue;
                if(l[i]<=bg && r[i]>=ed){
                    chkq(i)?ans[i]+=blk[0].sum:(sol(i),0);
                    continue;
                }
                if(l[i]<=bg){
                    part(bg,r[i],i);
                    continue;
                }
                if(r[i]>=ed){
                    part(l[i],ed,i);
                    continue;
                }
                part(l[i],r[i],i);
            }
        }
    }
    for(int i=1;i<=m;++i)
        if(chkq(i))printf("%lld\n",ans[i]);
    return 0;
}

然而时间也有 8 倍常数，而且基本一定是跑满的，所以甚至跑不过线段树做法（