莫隊算法詳解
DQUERY - D-query
題意：
求區(qū)間內(nèi)不同元素的數(shù)量宅倒，也就是求出現(xiàn)次數(shù)>=1的元素個數(shù)
#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,是為了剛開始移動時不會加到非法的區(qū)間
res=0;
for(int i=0;i<m;i++)
{// 由于初始區(qū)間 l >r ,所以下面循環(huán)得從r 開始扼睬，
//如果查詢區(qū)間不是從1開始就會出現(xiàn)l經(jīng)過一段，r重復經(jīng)過這一段跨释。
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)
題意：
在區(qū)間內(nèi)選出一對相同顏色的襪子的概率
題解：
假設區(qū)間[L,R]有y種顏色的襪子，分別為a,b,c...x,那么從[L,R]任選兩個襪子的組合數(shù)為C(R-L+1,2)=(R-L+1)*(R-L)/2;選出為a顏色的襪子組合數(shù)為C(a,2)=a*(a-1)/2,...選出為x顏色的襪子組合數(shù)為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 :求區(qū)間相同數(shù)字個數(shù)的立方和
Mato的文件管理
題意：
給定若干個區(qū)間厌处，求出逆序數(shù)
題解：
用數(shù)狀數(shù)組維護逆序數(shù)的變化
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int MAXN=50010;
/*數(shù)狀數(shù)組*/
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
題意：
求區(qū)間的不同的排列方式鳖谈，同時，區(qū)間內(nèi)有重復的數(shù)字
題解：
假設區(qū)間L,R內(nèi)有x種數(shù)字n,分別為n1,n2,n3..nx阔涉，那么排列方式為(R-L+1)!/(n1!*n2!...nx!)
這里由于數(shù)值很大缆娃，結(jié)果取模，所以用到了乘法逆元
#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]);
}
}
}
