BZOJ2038 小z的袜子

时间：2022-03-29 22:19:35

题意：给一些数，然后每次询问一段区间，问从这个区间中抽走两个数，抽到相同的数的概率

正解：莫队算法

今天新学习了莫队算法，感觉好神，离线的询问好像都可以用莫队。

要不是坑爹的HNOI2016考了两道莫队题，才不得不来入这个坑，A完这道题，就去A掉HNOI2016Day2的两道题。。。

 

把询问离线下来，然后按照左端点所在块的编号来排序，若在同一个块则以右端点编号排序（有点像分块）

然后我每次暴力处理一下一个询问，之后利用这一次的结果，往前或者往后拓展，把处在同一个块的全部都可以处理掉（期望复杂度：O（1））

最终可以达到O(N^1.5）的复杂度

复杂度证明的话，感觉yy一下可以想得到

 

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 int n,m;

 int color[MAXN];

 LL ans[MAXM];

 int siz,zong;

 LL size[MAXN];

 LL num[MAXN];

 //莫队算法

 struct wen{

     int l,r;

     int jilu;

     int k;//存储所在块的编号

 }Q[MAXM];

 inline int getint()

 {

        int w=,q=;

        char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar();

        if (c=='-')  q=, c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar();

        return q ? -w : w;

 }

 bool cmp(wen q,wen qq){ if(q.k==qq.k) return q.r<qq.r; return q.k<qq.k;  }

 //按照左端点所在块的编号来排序，若相等则以右端点编号为序

 inline LL gcd(LL x,LL y) { return y==? x:gcd(y,x%y); }

 int main()

 {

     freopen("hose.in","r",stdin);

     freopen("hose.out","w",stdout);

     n=getint();m=getint();

     for(int i=;i<=n;i++) color[i]=getint();

     zong=sqrt(n); if(zong*zong==n) siz=zong; else siz=n/zong+;

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

     Q[i].l=getint(),Q[i].r=getint(),Q[i].jilu=i,size[i]=Q[i].r-Q[i].l+;

     Q[i].k=(Q[i].l-)/siz+;

     }

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

     int ljh=;

     while(ljh<=m) {

     int kuai=Q[ljh].k;

     memset(num,,sizeof(num));

     for(int j=Q[ljh].l;j<=Q[ljh].r;j++) ans[Q[ljh].jilu]+=*(num[color[j]]++);

     ljh++;

     for(;Q[ljh].k==kuai;ljh++) {

         ans[Q[ljh].jilu]=ans[Q[ljh-].jilu];

         for(int j=Q[ljh-].r+ ;j<=Q[ljh].r;j++) ans[Q[ljh].jilu]+=*(num[color[j]]++);

         if(Q[ljh].l>Q[ljh-].l) for(int j=Q[ljh-].l;j<Q[ljh].l;j++) ans[Q[ljh].jilu]-=*(--num[color[j]]);

         else for(int j=Q[ljh].l;j<Q[ljh-].l;j++) ans[Q[ljh].jilu]+=*(num[color[j]]++);

     }

     }

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

     LL fenmu;

     if(size[i]==) fenmu=;

     else fenmu=size[i]*(size[i]-);

     LL gong=gcd(fenmu,ans[i]);

     printf("%lld/%lld\n",ans[i]/gong,fenmu/gong);

     }

     return ;

 }

相关文章