洛谷 P1494 [国家集训队]小Z的袜子（莫队）

题目链接：https://www.luogu.com.cn/problem/P1494

一道很经典的莫队模板题，然而每道莫队题的大体轮廓都差不多。

首先莫队是一种基于分块的算法，它的显著特点就是：

能在$O(1)$的时间内从$(l,r)$转换到$(l,r-1),(l-1,r),(l+1,r),(l,r+1)$。

然后它的总复杂度在$O(n\times \sqrt{n})$左右。

这道题中除了莫队的应用外，还需要处理一个组合数$(cul)$和一个$gcd$，然后跑莫队即可。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int N=+;

 int a[N],vis[N];

 int ans1[N],ans2[N];

 ll ans;

 int block;

 struct node{

     int l,r;

     int id;

 }q[N];

 ll cul(ll x){

     return x*(x-)/;

 }

 bool cmp(node aa,node bb){

     if(aa.l/block==bb.l/block) return aa.r<bb.r;

     return aa.l/block<bb.l/block;

 }

 void add(int pos){

     vis[a[pos]]++;

     ll m=vis[a[pos]];

     ans=ans-cul(m-)+cul(m);

 }

 void del(int pos){

     vis[a[pos]]--;

     ll m=vis[a[pos]];

     ans=ans-cul(m+)+cul(m);

 }

 int gcd(int n,int m){

     if(m==) return n;

     return gcd(m,n%m);

 }

 int main(){

     int n,m;

     scanf("%d%d",&n,&m);

     block=sqrt(n);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     int L=,R=;

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

         scanf("%d%d",&q[i].l,&q[i].r);

         q[i].id=i;

     }

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

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

         while(L<q[i].l){

             del(L);

             L++;

         }

         while(L>q[i].l){

             L--;

             add(L);

         }

         while(R>q[i].r){

             del(R);

             R--;

         }

         while(R<q[i].r){

             R++;

             add(R);

         }

         ans1[q[i].id]=ans;

         ans2[q[i].id]=cul(q[i].r-q[i].l+);

     }

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

         int g=gcd(ans1[i],ans2[i]);

         if(ans1[i]==){

             printf("0/1\n");

             continue;

         }

         printf("%d/%d\n",ans1[i]/g,ans2[i]/g);

     }

     return ;

 }

AC代码

巴特西

洛谷 P1494 [国家集训队]小Z的袜子（莫队）

最新文章

热门文章