莫队首发——小Z的袜子+分块

向右看齐 2021-12-18 13:57 196阅读 0赞

嫖别人的博客解释是不好的，可是我又懒得写，毕竟我只是想留留板子

所以附上别人的博客链接，写的真不错呀

[https://www.cnblogs.com/Paul-Guderian/p/6933799.html][https_www.cnblogs.com_Paul-Guderian_p_6933799.html]

这题改了一天多的bug，还一度开始怀疑人生了，毕竟我看着别人的代码带着自己的理解写的，现在不会弱到抄都抄不对吧！！！最后发现自己就是个大傻逼

几点失误

1.scanf确实是比cin快的，哪怕加了iOS：：，还是scanf快一筹

2.局部变量覆盖全局变量（第二次载这上面了，第一次是那次的裸分块题）

3.那个return的写法确实很快，因为每组数据都是nlogn次比较，快的真不少

给下题目链接，还有留留莫队板子

其实就是排个序，o1修改每点变化，排序是灵魂

题目链接[https://www.lydsy.com/JudgeOnline/problem.php?id=2038][https_www.lydsy.com_JudgeOnline_problem.php_id_2038]

我的代码

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e4+7;
    long long n,ans,l,r;
    long long cnt[N],a[N];
    long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}
    struct node
    {
        long long l,r,yuan,ans;
    }s[N];
    long long pos[N];
    void build()
    {
        long long block=ceil(sqrt(n));
        for(int i=1;i<=n;i++)
            pos[i]=((i-1)/block)+1;
        for(int i=1;i<=N;i++)
             cnt[i]=0,a[i]=0;
            l=1;r=0;
            ans=0;
    }
    bool cmp(node x,node y){return pos[x.l]<pos[y.l]||(pos[x.l]==pos[y.l]&&x.r<y.r);}
    bool cmp2(node x,node y)
    {
        return x.yuan<y.yuan;
    }
    int work(int L,int R)
    {
        while(r<R){r++; ans+=cnt[a[r]]  ; cnt[a[r]]++;}
        while(l>L){l--; ans+=cnt[a[l]]  ; cnt[a[l]]++;}
        while(l<L){cnt[a[l]]--;  ans-=cnt[a[l]];  l++;}
        while(r>R){cnt[a[r]]--;  ans-=cnt[a[r]];  r--;}
        //cout<<ans<<endl;
        return ans;
    }
    
    int main()
    {
        //ios::sync_with_stdio(false);
        long long m;
        while(~scanf("%lld%lld",&n,&m))
        {
            build();
            for(int i=1;i<=n;i++)
                scanf("%lld",&a[i]);
    
                //cin>>a[i];
            for(int i=0;i<m;i++)
            {
                scanf("%lld%lld",&s[i].l,&s[i].r);
                //cin>>s[i].l>>s[i].r;
                s[i].yuan=i;
                s[i].ans=0;
            }
            sort(s,s+m,cmp);
            //for(int i=0;i<m;i++) cout<<s[i].l<<' '<<s[i].r<<' '<<s[i].yuan<<endl;
            for(int i=0;i<m;i++)
            s[i].ans=work(s[i].l,s[i].r);
            sort(s,s+m,cmp2);
            for(int i=0;i<m;i++)
            if(s[i].ans==0)
            printf("0/1\n");
            else
            {
              long long kkk=(s[i].r-s[i].l+1)*(s[i].r-s[i].l)/2;
            printf("%lld/%lld\n",s[i].ans/gcd(s[i].ans,kkk),kkk/gcd(s[i].ans,kkk));
              //cout<<s[i].ans/gcd(s[i].ans,kkk)<<'/'<<kkk/gcd(s[i].ans,kkk)<<endl;
            }
        }
    }

分块算法一直以为都被誉为优雅的暴力

就是把n长的数组划分为sqrt n块，每块用两个数组保存，一个原数组，一个排个序，就能节约很多时间

举个例题 [https://loj.ac/problem/6278][https_loj.ac_problem_6278]

给出一个长为n 的数列，以及n 个操作，操作涉及区间加法，询问区间内小于某个值 的元素个数。

输入格式

第一行输入一个数字 n。

第二行输入 n个数字，第 i个数字为ai ，以空格隔开。

接下来输入 行询问，每行输入四个数字 a、b 、c 、 d，以空格隔开。

若a=1 ，表示将位于 b的c之间的数字都加d 。

若 a=2，表示询问 b中c，小于 d\*d的数字的个数。

分块暴力裸板子题，所以这篇主要就是为了保留下板子

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e4+7;
    long long n,block,num;
    long long a[N],belong[N],d[N];
    long long l[N],r[N],p[N];
    void build()
    {
        block=sqrt(n);
        num=n/block;
        if(n%block) num++;
        for(int i=1;i<=n;i++)
            belong[i]=((i-1)/block)+1;
        //for(int i=1;i<=n;i++)cout<<i<<' '<<belong[i]<<endl;
        for(int i=1;i<=num;i++)
        {
            l[i]=(i-1)*block+1;
            r[i]=i*block;
        }
        r[num]=n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            d[i]=a[i];
        }
        for(int i=1;i<=num;i++)
            sort(d+l[i],d+r[i]+1);
    }
    void add(int z,int y,long long k)
    {
        if(belong[z]==belong[y])
        {
            for(int i=z;i<=y;i++)
                a[i]+=k;
            for(int i=l[belong[z]];i<=r[belong[z]];i++)
                d[i]=a[i];
            sort(d+l[belong[z]],d+r[belong[z]]+1);
             return;
        }
        ///都在一块的情况
        for(int i=z;i<=r[belong[z]];i++)
            a[i]+=k;
        for(int i=l[belong[z]];i<=r[belong[z]];i++)
            d[i]=a[i];
        sort(d+l[belong[z]],d+r[belong[z]]+1);
        ///左残块
        for(int i=l[belong[y]];i<=y;i++)
            a[i]+=k;
        for(int i=l[belong[y]];i<=r[belong[y]];i++)
            d[i]=a[i];
        sort(d+l[belong[y]],d+r[belong[y]]+1);
        ///右残块
        for(int i=belong[z]+1;i<belong[y];i++)
            p[i]+=k;
        ///中间p数组维护
    }
    void query(int z,int y,long long c)
    {
        long long ans=0;
        if(belong[z]==belong[y])
        {
            for(int i=z;i<=y;i++)
                if(a[i]<c-p[belong[z]])
                    ans++;
            cout<<ans<<endl;
             return;
        }
        for(int i=z;i<=r[belong[z]];i++)
            if(a[i]<c-p[belong[z]])
                    ans++;
        for(int i=l[belong[y]];i<=y;i++)
            if(a[i]<c-p[belong[y]])
                    ans++;
        for(int i=belong[z]+1;i<belong[y];i++)
        {
            long long hh=c-p[i];
            ans+=lower_bound(d+l[i],d+r[i]+1,hh)-(d+l[i]);
        }
        cout<<ans<<endl;
    }
    int main()
    {
        cin>>n;
        ios::sync_with_stdio(false);
        build();
        int m=n;
        while(m--)
        {
            long long a1,a2,a3,a4;
            cin>>a1>>a2>>a3>>a4;
            if(a1==0)
                add(a2,a3,a4);
            else if(a1==1)
                query(a2,a3,a4*a4);
        }
    }

还有lower\_bound和upper\_bound

第一个返回第一个大于等于的地址

第二个返回大于的地址

再加个分块入门8的代码，哼别人找我debug，我没找到bug，然后用他的想法写了一遍，然后我一发入魂，就很nice

题干：

给出一个长为n 的数列，以及 n个操作，操作涉及区间询问等于一个数 c的元素，并将这个区间的所有元素改为 c。

输入格式

第一行输入一个数字 n。

第二行输入 n个数字，第 i 个数字为ai ，以空格隔开。

接下来输入n 行询问，每行输入三个数字l 、r 、c ，以空格隔开。

表示先查询位于 l-r的数字有多少个是c ，再把位于 l-r的数字都改为 c。

AC代码

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+7;
    int n,block,num;
    int a[N],belong[N];
    int p[1007],l[1007],r[1007];
    void build()
    {
        block=sqrt(n);
        num=n/block;
        if(n%block) num++;
        for(int i=1;i<=n;i++)
            belong[i]=((i-1)/block)+1;
        for(int i=1;i<=num;i++)
        {
            l[i]=(i-1)*block+1;
            r[i]=i*block;
            p[i]=-1;
        }
        r[num]=n;
    }
    void query(int L,int R,int c)
    {
        int ans=0;
        if(belong[L]==belong[R])
        {
            if(p[belong[L]]==c)
                ans+=R-L+1;
            else
            {
                if(p[belong[L]]!=-1)
                {
                    for(int i=l[belong[L]];i<=r[belong[L]];i++)
                    {
                        if(i>=L&&i<=R)
                            a[i]=c;
                        else
                            a[i]=p[belong[L]];
                    }
                    p[belong[L]]=-1;
                }
                else
                {
                    for(int i=L;i<=R;i++)
                        if(a[i]==c)
                            ans++;
                        else
                            a[i]=c;
                }
            }
            cout<<ans<<endl;
            return ;
        }
        ///在一块的情况
        if(p[belong[L]]==c)
            ans+=r[belong[L]]-L+1;
        else
        {
            if(p[belong[L]]!=-1)
            {
                for(int i=l[belong[L]];i<L;i++)
                a[i]=p[belong[L]];
                for(int i=L;i<=r[belong[L]];i++)
                a[i]=c;
                p[belong[L]]=-1;
            }
            else
            {
                for(int i=L;i<=r[belong[L]];i++)
                    if(a[i]==c)
                    ans++;
                else
                    a[i]=c;
            }
        }
        ///左残块处理完毕
        if(p[belong[R]]==c)
            ans+=R-l[belong[R]]+1;
        else
        {
            if(p[belong[R]]!=-1)
            {
                for(int i=l[belong[R]];i<=R;i++)
                a[i]=c;
                for(int i=R+1;i<=r[belong[R]];i++)
                a[i]=p[belong[R]];
                p[belong[R]]=-1;
            }
            else
            {
                for(int i=l[belong[R]];i<=R;i++)
                    if(a[i]==c)
                    ans++;
                else
                    a[i]=c;
            }
        }
        for(int i=belong[L]+1;i<belong[R];i++)
        {
            if(p[i]==c)
                ans+=block;
            else if(p[i]!=-1)
                p[i]=c;
            else
            {
                for(int j=l[i];j<=r[i];j++)
                    if(a[j]==c)
                    ans++;
                    else
                    a[j]=c;
                p[i]=c;
            }
        }
        cout<<ans<<endl;
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        build();
        int m=n;
        while(m--)
        {
            int a1,a2,a3;
            cin>>a1>>a2>>a3;
            query(a1,a2,a3);
        }
    }

[https_www.cnblogs.com_Paul-Guderian_p_6933799.html]: https://www.cnblogs.com/Paul-Guderian/p/6933799.html
[https_www.lydsy.com_JudgeOnline_problem.php_id_2038]: https://www.lydsy.com/JudgeOnline/problem.php?id=2038
[https_loj.ac_problem_6278]: https://loj.ac/problem/6278