题意
给出包含n个数字的序列,和m个查询。每次查询问区间[l,r]中挑选出两个数字,大小相同的概率为多少。
分析
莫队的入门题吧。代码是非常好写,关键是时间复杂度的证明。O(n*sqrt(n))。我还有点迷糊,等我再做几个题再说···
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath> using namespace std;
typedef long long LL;
const int maxn=+;
int val[maxn],belong[maxn],f[maxn];
int n,m,cnt,block;
LL gcd(LL a,LL b){
if(!b)return a;
return gcd(b,a%b);
} struct Node{
int L,R,id;
bool operator<(const Node& rhs)const{
return belong[L]<belong[rhs.L]||(belong[L]==belong[rhs.L]&&R<rhs.R);
}
LL a,b;
void solve(){
LL r=gcd(a,b);
a/=r,b/=r;
}
}ask[maxn];
int cmp(Node a,Node b){
return a.id<b.id;
}
LL ans;
void update(int p,int addv){
ans=ans+*addv*f[val[p]]+;
f[val[p]]+=addv;
} int main(){
scanf("%d%d",&n,&m);
memset(f,,sizeof(f));
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
block=sqrt(n);
cnt=n/block;
if(n%block)cnt++;
for(int i=;i<=n;i++){
belong[i]=(i-)/block+;
}
for(int i=;i<=m;i++){
scanf("%d%d",&ask[i].L,&ask[i].R);
ask[i].id=i;
} sort(ask+,ask++m);
ans=;
int l=,r=;
for(int i=;i<=m;i++){
if(r<ask[i].R){
for(r=r+;r<ask[i].R;r++){
update(r,);
}
update(r,);
}
if(l>ask[i].L){
for(l=l-;l>ask[i].L;l--){
update(l,);
}
update(l,);
}
if(r>ask[i].R){
for(;r>ask[i].R;r--){
update(r,-);
}
}
if(l<ask[i].L){
for(;l<ask[i].L;l++){
update(l,-);
}
}
if(ask[i].L==ask[i].R){
ask[i].a=,ask[i].b=;
continue;
}
ask[i].a=ans-(ask[i].R-ask[i].L+),ask[i].b=(LL)(ask[i].R-ask[i].L+)*(ask[i].R-ask[i].L);
ask[i].solve();
}
sort(ask+,ask++m,cmp);
for(int i=;i<=m;i++){
printf("%lld/%lld\n",ask[i].a,ask[i].b);
}
return ;
}