莫队算法详解
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]);
}
}
}
网友评论