莫队算法

莫队算法详解
 DQUERY - D-query
题意：
求区间内不同元素的数量，也就是求出现次数>=1的元素个数

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=30010;
const int MAXQ=200010;
const int BOUND=1e6+10;
int pos[MAXN];
int num[MAXN];
int ans[MAXQ];
int cnt[BOUND];
int res;
struct Query
{
    int lef,rig,id;
    bool operator <(const Query &t) const
    {
        if(pos[lef]==pos[t.lef]) return rig<t.rig;
        return pos[lef]<pos[t.lef];
    }
};
void add(int position)
{
    cnt[num[position]]++;
    if(cnt[num[position]]==1) res++;
}
void dele(int position)
{
    cnt[num[position]]--;
    if(cnt[num[position]]==0) res--;
}
Query query[MAXQ];
int main()
{
    int n,m,blocks;
    scanf("%d",&n);
    blocks=ceil(sqrt(n));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",num+i);
        pos[i]=(i-1)/blocks;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&query[i].lef,&query[i].rig);
        query[i].id=i;
    }
    sort(query,query+m);
    memset(cnt,0,sizeof(cnt));
    int currL=1,currR=0;//currL为1,currR为0,是为了刚开始移动时不会加到非法的区间
    res=0;
    for(int i=0;i<m;i++)
    {// 由于初始区间 l >r ,所以下面循环得从r 开始，
    //如果查询区间不是从1开始就会出现l经过一段，r重复经过这一段。
        while(currR<query[i].rig) {currR++; add(currR);  }
        while(currR>query[i].rig) {dele(currR);currR--;}
        while(currL<query[i].lef) { dele(currL);currL++; }
        while(currL>query[i].lef) { add(currL-1);currL--; }
        ans[query[i].id]=res;
    }
    for(int i=0;i<m;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}

小Z的袜子(hose)
题意：
在区间内选出一对相同颜色的袜子的概率
题解：
假设区间[L,R]有y种颜色的袜子，分别为a,b,c...x,那么从[L,R]任选两个袜子的组合数为C(R-L+1,2)=(R-L+1)*(R-L)/2;选出为a颜色的袜子组合数为C(a,2)=a*(a-1)/2,...选出为x颜色的袜子组合数为C(x,2)=x*(x-1)/2,
所以概率为（C(a,2)＋C(b,2)．．．+C(x,2)）/（C(R-L+1,2)）
＝( a*(a-1)+b*(b-1)+...+x*(x-1) )/ ( (R-L+1)*(R-L) )
=(a*a+b*b+...+x*x-(a+b+c...+x) )/ ( (R-L+1)*(R-L) )
而(a+b+c...+x)＝(R-L+1)
所以概率为(a*a+b*b+...+x*x-(R-L+1) )/ ( (R-L+1)*(R-L) )

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=50010;
long long cnt[MAXN];
int pos[MAXN];
long long num[MAXN];
long long ans1[MAXN];
long long ans2[MAXN];
long long sum,gg;
struct Query
{
    int lef,rig,id;
    bool operator<(const Query &l) const
    {
        if(pos[lef]==pos[l.lef]) return rig<l.rig;
        return pos[lef]<pos[l.lef];
    }
};
Query query[MAXN];
void add(int position)
{
    sum-=cnt[num[position]]*cnt[num[position]];
    cnt[num[position]]++;
    sum+=cnt[num[position]]*cnt[num[position]];
}
void del(int position)
{
    sum-=cnt[num[position]]*cnt[num[position]];
    cnt[num[position]]--;
    sum+=cnt[num[position]]*cnt[num[position]];
}
long long gcd(long long a,long long b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int n,m,blocks;
    scanf("%d%d",&n,&m);
    blocks=ceil(sqrt(n));
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",num+i);
        pos[i]=(i-1)/blocks;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&query[i].lef,&query[i].rig);
        query[i].id=i;
    }
    sort(query,query+m);
    memset(cnt,0,sizeof(cnt));
    int currL=1,currR=0,L,R;
    sum=0;
    for(int i=0;i<m;i++)
    {
        L=query[i].lef;R=query[i].rig;
        while(currR>R) {del(currR);currR--;}
        while(currR<R) { currR++; add(currR);}
        while(currL<L){ del(currL);currL++;}
        while(currL>L) {add(currL-1);currL--;}
        long long up=sum-(long long)(query[i].rig-query[i].lef+1);
        long long down=(long long)(query[i].rig-query[i].lef+1)*(long long)(query[i].rig-query[i].lef);
        gg=gcd(up,down);
        ans1[query[i].id]=up/gg;
        ans2[query[i].id]=down/gg;
    }
    for(int i=0;i<m;i++)
    {
        printf("%lld/%lld\n",ans1[i],ans2[i]);
    }
    return 0;
}

类似题目：
G - Sona :求区间相同数字个数的立方和

Mato的文件管理
题意：
给定若干个区间，求出逆序数
题解：
用数状数组维护逆序数的变化

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int MAXN=50010;
/*数状数组*/
int c[MAXN],n;
int lowbit(int x){ return x&(-x);}
void add(int x,int val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
/*莫队算法*/
int cpy[MAXN],num[MAXN],pos[MAXN],ans[MAXN],currSum;
struct Query
{
    int lef,rig,id;
    bool operator<(const Query& t) const
    {
        if(pos[lef]==pos[t.lef]) return rig<t.rig;
        return pos[lef]<pos[t.lef];
    }
};
Query query[MAXN];
int main()
{
    int m,blocks;
    scanf("%d",&n);
    blocks=ceil(sqrt(n));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        cpy[i]=num[i];
        pos[i]=i/blocks;
    }
    sort(cpy+1,cpy+1+n);
    for(int i=1;i<=n;i++)//离散化
    {
        num[i]=lower_bound(cpy+1,cpy+1+n,num[i])-cpy;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&query[i].lef,&query[i].rig);
        query[i].id=i;
    }
    sort(query,query+m);
    int currL=1,currR=0,L,R;
    currSum=0;
    for(int i=0;i<m;i++)
    {
        L=query[i].lef;R=query[i].rig;
        while(currR<R)
        {
            currR++;
            add(num[currR],1);
            currSum+=currR-currL+1-sum(num[currR]);
        }
        while(currR>R)
        {
            currSum-=currR-currL+1-sum(num[currR]);
            add(num[currR],-1);
            currR--;
        }
        while(currL<L)
        {
           add(num[currL],-1);
           currSum-=sum(num[currL]-1);
           currL++;
        }
        while(currL>L)
        {
            currL--;
            add(num[currL],1);
            currSum+=sum(num[currL]-1);
        }
        ans[query[i].id]=currSum;
    }
    for(int i=0;i<m;i++)
    {
        printf("%d\n",ans[i]);
    }
}

E - NPY and girls
题意：
求区间的不同的排列方式，同时，区间内有重复的数字
题解：
假设区间L,R内有x种数字n,分别为n1,n2,n3..nx，那么排列方式为(R-L+1)!/(n1!*n2!...nx!)
这里由于数值很大，结果取模，所以用到了乘法逆元

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b){ d=a;x=1;y=0;}
    else
    {
        gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
LL inv(LL a,LL n)
{
    LL d,x,y;
    gcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}
/*莫队算法*/
const int MAXN=30010;
const LL MOD=1000000007;
int pos[MAXN];
int num[MAXN];
LL cnt[MAXN];
LL ans[MAXN];
LL inver[MAXN];
LL res;
struct Query
{
    int l,r,id;
    bool operator<(const Query &que) const
    {
        if(pos[l]==pos[que.l]) return r<que.r;
        return pos[l]<pos[que.l];
    }
};
Query query[MAXN];
void add(int position,LL len)
{
    res=res*len%MOD;
    cnt[num[position]]++;
    res=res*inver[cnt[num[position]]]%MOD;
}
void del(int position,LL len)
{
    res=res*inver[len]%MOD;
    res=res*cnt[num[position]]%MOD;
    cnt[num[position]]--;
}
int main()
{
    int t,n,m,blocks;
    scanf("%d",&t);
    for(long long i=1;i<MAXN;i++)
    {
        inver[i]=inv(i,MOD);
    }
    while(t--)
    {
        scanf("%d%d",&n,&m);
        blocks=ceil(sqrt(n+0.0));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",num+i);
            pos[i]=(i-1)/blocks;
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&query[i].l,&query[i].r);
            query[i].id=i;
        }
        sort(query,query+m);
        int currL=1,currR=0,L,R;
        res=1;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<m;i++)
        {
            L=query[i].l;R=query[i].r;
            while(currR<R)
            {
                currR++;
                add(currR,currR-currL+1);
            }
            while(currR>R)
            {
                del(currR,currR-currL+1);
                currR--;
            }
            while(currL<L)
            {
                del(currL,currR-currL+1);
                currL++;
            }
            while(currL>L)
            {
                currL--;
                add(currL,currR-currL+1);
            }
            ans[query[i].id]=res;
        }
        for(int i=0;i<m;i++)
        {
            printf("%lld\n",ans[i]);
        }
    }
}

推荐阅读更多精彩内容