搜索

根号算法学习记录


发布时间: 2022-11-24 18:24:05    浏览次数:35 次

根号算法专题

分块基础

根号平衡

对于两个不同方面的复杂度,直接做的话一个很小,一个很大,我们用根号使得两者复杂度同阶级以降低总复杂度。这个叫根号平衡。

一个典型的应用是根号分治。打个比方我们想 \(O(n)\) 以下复杂度统计序列从某一位下标等差的一种前缀和,我们全部预处理空间复杂度是 \(O(n^2)\) ,时间复杂度也是 \(O(n^2)\) 的,这样做一次是 \(O(n)\)。直接暴力做求一次是 \(O(\frac{n}{x})\)\(x\) 是下标公差)。这个我们可以两者折中,预处理 \(x<\sqrt n\) 的(做一次 \(O(1)\),预处理 \(O(n\sqrt n)\)),暴力算 \(x\ge \sqrt n\) 的(做一次 \(O(\sqrt n)\))。

后面我们的很多根号算法都是基于这个思想,即取一个值来平衡两个极端的复杂度。

是大致这么个思想,具体应用往下。

最为简单的分块

题目:维护区间加查询、区间加修改。

把序列分块,完整的块打标记,零散的块暴力进行。

设块长为 \(B\) ,单次操作复杂度整块 \(O(\frac{n}{B})\) ,零散块 \(O(B)\) 。考虑根号平衡,取 \(B=\sqrt n\) ,总复杂度 \(O(\sqrt n)\)

稍微雷一点的分块

题目:维护区间加、区间查询排名

分块,然后维护块内排序后数组。修改时整块打标记,散块重构。查询每个块内排序数组上直接二分。

设块长为 \(B\)

查询复杂度:整块 \(O(\frac{n}{B}\log{B})\) ,散块 \(O(B)\)

修改复杂度:整块 \(O(\frac{n}{B})\) ,散块 \(O(B)\)。(散块的重构用归并)

我们让查询和修改的整块与散块复杂度根号平衡,取块长 \(B=\sqrt{n\log n}\) ,总复杂度 \(O(n\sqrt{n\log n})\)

再看下面这个:

[Ynoi2017] 由乃打扑克

这里是上面的查询变为查询第 \(k\) 小,如果直接套用上面的套路,复杂度需要多一个二分答案的 \(\log\) ,会被卡掉,不行。

改块长,令 \(B=\sqrt n \log n\) ,除了散块复杂度单次操作全都变为根号以下。因为查询外层套的二分,我们只需考虑优化查询的散块复杂度。先把两边散块临时合并,之后每次在上面二分即可。

总复杂度 \(O(n\sqrt n \log n)\)

注,我们实际取块长时并不直接取理论复杂度,而是类似手动模拟退火。

#include<bits/stdc++.h>
#define ll long long
#define db double
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define sky fflush(stdout)
#define gc getchar
#define pc putchar
namespace IO{
    template<class T>
    inline void read(T &s){
        s=0;char ch=gc();bool f=0;
        while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
        while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
        if(ch=='.'){
            T p=0.1;ch=gc();
            while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p/=10;ch=gc();}
        }
        s=f?-s:s;
    }
    template<class T,class ...A>
    inline void read(T &s,A &...a){
        read(s);read(a...);
    }
};
using IO::read;
const int N=1e5+3;
const int B=328;
int n,m;
int a[N];
int bl[N];
struct Block{
    inline int len(){
        return ed-st+1;
    }
    int st,ed;
    int el,er,ela;
    int add;
    struct node{
        int x,p;
    }ov[B+3];
}b[(N-3)/B+3];
//int tim2,t,tim1,tim3,tim4;
Block::node tmp1[N],tmp2[N];
inline void MergeSort(Block::node *ans,int n,int m){
    int l=1,r=1;
    for(int i=1;i<=n+m;++i){
        if((l<=n and tmp1[l].x<tmp2[r].x) or r>m){
            ans[i]=tmp1[l];++l;
        }else{
            ans[i]=tmp2[r];++r;
        }
    }
}
inline void modify(int l,int r,int k){
    if(bl[l]==bl[r]){
        //t=clock();
        for(int i=l;i<=r;++i){
            a[i]+=k;
        }
        int top1=0,top2=0;
        for(int i=b[bl[l] ].st;i<=b[bl[l] ].ed;++i){
            if(
                l<=b[bl[l] ].ov[i-b[bl[l] ].st+1].p and 
                b[bl[l] ].ov[i-b[bl[l] ].st+1].p<=r
            ){
                tmp1[++top1]=b[bl[l] ].ov[i-b[bl[l] ].st+1];
                tmp1[top1].x+=k;
            }else{
                tmp2[++top2]=b[bl[l] ].ov[i-b[bl[l] ].st+1];
            }
        }
        MergeSort(b[bl[l] ].ov,top1,top2);
        //tim1+=clock()-t;
        return;
    }
    //t=clock();
    for(int i=bl[l]+1;i<=bl[r]-1;++i){
        b[i].add+=k;
    }
    //tim2+=clock()-t;
    //t=clock();
    for(int i=l;i<=b[bl[l] ].ed;++i){
        a[i]+=k;
    }
    int top1=0,top2=0;
    for(int i=b[bl[l] ].st;i<=b[bl[l] ].ed;++i){
        if(l<=b[bl[l] ].ov[i-b[bl[l] ].st+1].p){
            tmp1[++top1]=b[bl[l] ].ov[i-b[bl[l] ].st+1];
            tmp1[top1].x+=k;
        }else{
            tmp2[++top2]=b[bl[l] ].ov[i-b[bl[l] ].st+1];
        }
    }
    MergeSort(b[bl[l] ].ov,top1,top2);
    for(int i=b[bl[r] ].st;i<=r;++i){
        a[i]+=k;
    }
    top1=0,top2=0;
    for(int i=b[bl[r] ].st;i<=b[bl[r] ].ed;++i){
        if(b[bl[r] ].ov[i-b[bl[r] ].st+1].p<=r){
            tmp1[++top1]=b[bl[r] ].ov[i-b[bl[r] ].st+1];
            tmp1[top1].x+=k;
        }else{
            tmp2[++top2]=b[bl[r] ].ov[i-b[bl[r] ].st+1];
        }
    }
    MergeSort(b[bl[r] ].ov,top1,top2);
    //tim1+=clock()-t;
}
bool first_time;
Block::node ov1[N];
int len1;
int el2,er2,ela2;
inline int query(int ql,int qr,int k,int uod){//小于等于k的数量    
    int ans=0;
    if(bl[ql]==bl[qr]){
        //t=clock();
        if(first_time){
            len1=0;
            for(int i=b[bl[ql] ].st;i<=b[bl[ql] ].ed;++i){
                if(
                    ql<=b[bl[ql] ].ov[i-b[bl[ql] ].st+1].p and 
                    b[bl[ql] ].ov[i-b[bl[ql] ].st+1].p<=qr
                ){
                    ov1[++len1]=b[bl[ql] ].ov[i-b[bl[ql] ].st+1];
                    ov1[len1].x+=b[bl[ql] ].add;
                }
            }
            el2=1;er2=len1;ela2=0;
            first_time=0;
        }
        int l=el2,r=er2,res=0;
        if(ov1[len1].x<=k){
            ela2=len1;
            return len1;
        }else if(ov1[1].x<=k){
            if(ela2){
                if(uod){
                    el2=l=ela2;
                }else{
                    er2=r=ela2;
                }
            }
            while(l<=r){
                int mid=(l+r)>>1;
                if(ov1[mid].x<=k){
                    l=mid+1;res=mid;
                }else{
                    r=mid-1;
                }
            }
            ela2=res;
            return res;
        }
        ela2=0;
        //tim3+=clock()-t;
        return 0;
    }
    //t=clock();
    if(first_time){
        int top1=0,top2=0;
        for(int i=b[bl[ql] ].st;i<=b[bl[ql] ].ed;++i){
            if(ql<=b[bl[ql] ].ov[i-b[bl[ql] ].st+1].p){
                tmp1[++top1]=b[bl[ql] ].ov[i-b[bl[ql] ].st+1];
                tmp1[top1].x+=b[bl[ql] ].add;
            }
        }
        for(int i=b[bl[qr] ].st;i<=b[bl[qr] ].ed;++i){
            if(b[bl[qr] ].ov[i-b[bl[qr] ].st+1].p<=qr){
                tmp2[++top2]=b[bl[qr] ].ov[i-b[bl[qr] ].st+1];
                tmp2[top2].x+=b[bl[qr] ].add;
            }
        }
        MergeSort(ov1,top1,top2);
        len1=top1+top2;
        el2=1;er2=len1;ela2=0;
        for(int i=bl[ql]+1;i<=bl[qr]-1;++i){
            b[i].el=1;b[i].er=b[i].len();
            b[i].ela=0;
        }
        first_time=0;
    }
    int l=el2,r=er2,res=0;
    if(ov1[len1].x<=k){
        ans+=len1;
        ela2=len1;
    }else if(ov1[1].x<=k){
        if(ela2){
            if(uod){
                el2=l=ela2;
            }else{
                er2=r=ela2;
            }
        }
        while(l<=r){ 
            int mid=(l+r)>>1;
            if(ov1[mid].x<=k){
                l=mid+1;res=mid;
            }else{
                r=mid-1;
            }
        }
        ela2=res;
        ans+=res;
    }else{
        ela2=0;
    }
    //tim3+=clock()-t;
    //t=clock();
    for(int i=bl[ql]+1;i<=bl[qr]-1;++i){
        l=b[i].el;r=b[i].er;res=0;
        if(b[i].ov[b[i].len()].x+b[i].add<=k){
            ans+=b[i].len();
            b[i].ela=b[i].len();
            continue;
        }else if(b[i].ov[1].x+b[i].add>k){
            b[i].ela=0;
            continue;
        }
        if(uod==1){
            b[i].el=l=std::max(l,b[i].ela);
        }else if(uod==0){
            b[i].er=r=std::min(r,b[i].ela);
        }
        while(l<=r){
            int mid=(l+r)>>1;
            if(b[i].ov[mid].x+b[i].add<=k){
                l=mid+1;res=mid;
            }else{
                r=mid-1;
            }
        }
        b[i].ela=res;
        ans+=res;
    }
    //tim4+=clock()-t;
    return ans;
}
inline int query_min(int ql,int qr){
    if(bl[ql]==bl[qr]){
        int res=(int)2e9;
        for(int i=ql;i<=qr;++i){
            res=std::min(res,a[i]+b[bl[ql] ].add);
        }
        return res;
    }
    int res=(int)2e9;
    for(int i=ql;i<=b[bl[ql] ].ed;++i){
        res=std::min(res,a[i]+b[bl[ql] ].add);
    }
    for(int i=b[bl[qr] ].st;i<=qr;++i){
        res=std::min(res,a[i]+b[bl[qr] ].add);
    }
    for(int i=bl[ql]+1;i<=bl[qr]-1;++i){
        res=std::min(res,b[i].ov[1].x+b[i].add);
    }
    return res;
}
inline int query_max(int ql,int qr){
    if(bl[ql]==bl[qr]){
        int res=(int)-2e9;
        for(int i=ql;i<=qr;++i){
            res=std::max(res,a[i]+b[bl[ql] ].add);
        }
        return res;
    }
    int res=(int)-2e9;
    for(int i=ql;i<=b[bl[ql] ].ed;++i){
        res=std::max(res,a[i]+b[bl[ql] ].add);
    }
    for(int i=b[bl[qr] ].st;i<=qr;++i){
        res=std::max(res,a[i]+b[bl[qr] ].add);
    }
    for(int i=bl[ql]+1;i<=bl[qr]-1;++i){
        res=std::max(res,b[i].ov[b[i].len()].x+b[i].add);
    }
    return res;
}
inline int kth(int ql,int qr,int k){//第k小
    first_time=1;
    if(k<=0 or k>qr-ql+1) return -1;
    int l=query_min(ql,qr),r=query_max(ql,qr),res=-1;
    if(k==1) return l;
    if(k==qr-ql+1) return r;
    int la=-2e9;
    while(l<=r){
        int mid=((ll)l+(ll)r)>>1;
        if(query(ql,qr,mid,(mid>=la) )<k){
            l=mid+1;
        }else{
            r=mid-1;res=mid;
        }
        la=mid;
    }
    return res;
}
int main(){
    //file(a);
    read(n,m);
    //B=std::max(1,(int)sqrt(n)*(int)log2(n) );
    //fprintf(stderr,"%d %d\n",B,(n-1)/B);
    for(int i=1;i<=n;++i){
        read(a[i]);
        bl[i]=(i-1)/B;
    }
    for(int i=0;i<=bl[n];++i){
        b[i].st=i*B+1;
        b[i].ed=std::min(n,(i+1)*B);
        for(int l=b[i].st;l<=b[i].ed;++l){
            b[i].ov[l-b[i].st+1]={a[l],l};
        }
        std::sort(b[i].ov+1,b[i].ov+1+b[i].len(),
            [](Block::node x,Block::node y){
                return x.x<y.x;
            }
        );
    }
    for(int i=1;i<=m;++i){
        int op,l,r,k;
        read(op,l,r,k);
        if(op==1){//query [l,r] k th
            printf("%d\n",kth(l,r,k) );
            //print(kth(l,r,k) );pc('\n');
        }else{//modify [l,r] add k
            modify(l,r,k);
        }
        /*
        for(int j=0;j<=bl[n];++j){
            fprintf(stderr,"[");
            for(int l=b[j].st;l<=b[j].ed;++l){
                fprintf(stderr,"%d ",a[l]+b[j].add);
            }fprintf(stderr,"] ");
        }fprintf(stderr,"\n");
        for(int j=0;j<=bl[n];++j){
            fprintf(stderr,"(");
            for(int l=b[j].st;l<=b[j].ed;++l){
                fprintf(stderr,"%d ",b[j].ov[l-b[j].st+1].x+b[j].add);
            }fprintf(stderr,") ");
        }fprintf(stderr,"\n");
        */
    }
    /*
    fprintf(stderr,"%dms\n",(int)clock() );
    fprintf(stderr,"modify full:%dms inco:%dms\n",tim2,tim1);
    fprintf(stderr,"query full:%dms inco:%dms\n",tim4,tim3);
    */
    return 0;
}

一些比较有意思的轻型分块

\(O(1)\) 区间加,\(O(\sqrt n)\) 单点查

分块维护差分。修改 \([l,r]\) 则在 \(l-1\) 处和 \(r\) 处分别打上 \(-k\) , \(+k\) 标记。查询的时候扫一遍即可。

\(O(\sqrt n)\) 插入,\(O(1)\)\(k\)

还是按照值域分块。同时维护第 \(i\) 大在哪个块里,对每个块中存在的数维护OV。

每次插入的时候对于所在块重构OV,并修改 \(\sqrt n\) 个第 \(i\) 大到前一个块中。这个复杂度是 \(O(\sqrt n)\) 的。

然后查询就是直接查所在块,然后再块内OV找到值即可。(因此还需要维护块间的数的个数前缀和)

一点练习题

就不给题解了,懒了。

动态分块。

Chef and Churu

序列

静态分块。

[Ynoi2019 模拟赛] Yuno loves sqrt technology I

[Ynoi2019 模拟赛] Yuno loves sqrt technology II

[Violet]蒲公英

[Ynoi2019 模拟赛] Yuno loves sqrt technology III

莫队

这个比较基础就不再赘述了。

一个对于同时维护多个区间的可以考虑差分。转换为一个多个只关于两个前缀的查询。

莫队二次离线

块状链表

真树分块

免责声明 根号算法学习记录,资源类别:文本, 浏览次数:35 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:24:05。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/cbdsopa/p/16809778.html