bzoj2038 小Z的袜子(hose)—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2038

就是莫队算法；

先写了个分块，惨WA：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=;

int n,m,K,c[maxn],rk[maxn],cnt[maxn],cnt2[maxn],ct=,t,tmp[maxn];

ll sum,s;

struct N{int l,r;ll ans,ans2;}q[maxn];

int rd()

{

    int ret=;char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret;

}

bool cmp(int x,int y){return q[x].l<q[y].l;}

bool cmp2(int x,int y){return q[x].r<q[y].r;}

int C(int x){return x*(x-)/;}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void yf(N &x)//&

{

    ll k=gcd(x.ans2,x.ans);

    x.ans/=k;x.ans2/=k;

}

void solve(int k)

{

    sort(tmp+,tmp+t+,cmp2);

    sum=;

    memset(cnt,,sizeof cnt);

    int L=k*K,R=L+;

    for(int i=;i<=t;i++)

    {

        memset(cnt2,,sizeof cnt2);

        while(R<=q[tmp[i]].r)

        {

            sum+=cnt[c[R]];cnt[c[R]]++;R++;

        }

        s=sum;

        for(int j=L;j>=q[tmp[i]].l;j--)

        {

            s+=cnt[c[j]]+cnt2[c[j]];cnt2[c[j]]++;

        }

        q[tmp[i]].ans=s;

        q[tmp[i]].ans2=C(q[tmp[i]].r-q[tmp[i]].l+);

        yf(q[tmp[i]]);

    }

}

int main()

{

    n=rd();m=rd();K=sqrt(n);

    for(int i=;i<=n;i++)c[i]=rd();

    for(int i=;i<=m;i++)q[i].l=rd(),q[i].r=rd(),rk[i]=i;

    sort(rk+,rk+m+,cmp);

    for(int i=;(i-)*K<n;i++)

    {

        t=;

        while(q[rk[ct]].l<=i*K&&ct<=m)tmp[++t]=rk[ct],ct++;

        solve(i);

    }

    for(int i=;i<=m;i++)

        printf("%lld/%lld\n",q[i].ans,q[i].ans2);

    return ;

}

囧

然后看了看题解，竟然是另一种做法，处理了一下式子：https://www.cnblogs.com/MashiroSky/p/5914637.html

所以抄了一下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=;

int n,m,K,c[maxn],cnt[maxn],blk[maxn];

ll ans;

struct N{int l,r,bh;ll a,b;}q[maxn];

int rd()

{

    int ret=;char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret;

}

bool cmp(N x,N y){return blk[x.l]==blk[y.l]?x.r<y.r:blk[x.l]<blk[y.l];}

bool cmp2(N x,N y){return x.bh<y.bh;}

ll gcd(ll a,ll b){return a%b==?b:gcd(b,a%b);}

void update(int x,int val)

{

    ans-=cnt[c[x]]*cnt[c[x]];

    cnt[c[x]]+=val;

    ans+=cnt[c[x]]*cnt[c[x]];

}

int main()

{

    n=rd();m=rd();K=sqrt(n);

    for(int i=;i<=n;i++)c[i]=rd(),blk[i]=(i-)/K+;;

    for(int i=;i<=m;i++)q[i].l=rd(),q[i].r=rd(),q[i].bh=i;

    sort(q+,q+m+,cmp);

    for(int i=,l=,r=;i<=m;i++)

    {

        while(l<q[i].l)update(l,-),l++;    while(l>q[i].l)update(l-,),l--;

        while(r<q[i].r)update(r+,),r++;    while(r>q[i].r)update(r,-),r--;

        if(q[i].l==q[i].r)

        {

            q[i].a=;q[i].b=;continue;

        }

        q[i].a=(ll)ans-(r-l+);    q[i].b=(ll)(r-l+)*(r-l);//(ll)!!!

        ll k=gcd(q[i].a,q[i].b);//把分子放前面，万一分子是0

        q[i].a/=k; q[i].b/=k;

    }

    sort(q+,q+m+,cmp2);

    for(int i=;i<=m;i++)

        printf("%lld/%lld\n",q[i].a,q[i].b);

    return ;

}

...

然后又看到一篇博客：https://www.cnblogs.com/xuwangzihao/p/5199174.html

我的想法还是可以的嘛，加入一个点就是增加了之前有的这种点个数那么多的点对，所以维护点的个数即可；

主要是这个题不用严格按照分块来做，只是按分块排一下序就可以保证时间复杂度了，所以 l 和 r 直接全局移动就可以；

这样的话代码突然变得好优美...说到底自己那样的分块还是写得太丑，都不能保证正确呢...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=;

int n,m,K,c[maxn],cnt[maxn],blk[maxn];

ll ans;

struct N{int l,r,bh;ll a,b;}q[maxn];

int rd()

{

    int ret=;char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret;

}

bool cmp(N x,N y){return blk[x.l]==blk[y.l]?x.r<y.r:blk[x.l]<blk[y.l];}

bool cmp2(N x,N y){return x.bh<y.bh;}

ll C(ll x){return x*(x-)/;}

ll gcd(ll a,ll b){return a%b==?b:gcd(b,a%b);}

void pop(int x){cnt[c[x]]--;ans-=cnt[c[x]];}//注意顺序

void push(int x){ans+=cnt[c[x]];cnt[c[x]]++;}

int main()

{

    n=rd();m=rd();K=sqrt(n);

    for(int i=;i<=n;i++)c[i]=rd(),blk[i]=(i-)/K+;

    for(int i=;i<=m;i++)q[i].l=rd(),q[i].r=rd(),q[i].bh=i;

    sort(q+,q+m+,cmp);

    for(int i=,l=,r=;i<=m;i++)

    {

        while(l<q[i].l)pop(l),l++;

        while(l>q[i].l)push(l-),l--;

        while(r<q[i].r)push(r+),r++;

        while(r>q[i].r)pop(r),r--;

        q[i].a=ans;

        q[i].b=C(r-l+);

        ll k=gcd(q[i].a,q[i].b);//把分子放前面，万一分子是0

        q[i].a/=k; q[i].b/=k;

    }

    sort(q+,q+m+,cmp2);

    for(int i=;i<=m;i++)

        printf("%lld/%lld\n",q[i].a,q[i].b);

    return ;

}

巴特西

bzoj2038 小Z的袜子(hose)——莫队算法

最新文章

热门文章