P1494 小Z的袜子
终于了解了莫队算法(更专业的名称Square Root Decomposition of Queries）
莫队算法:
- 一般来说解决静态(实际上也有修改的但复杂度更高)的离线(离线意味着需要知道所有查询)区间查询
- 我理解的特点是从区间[L,R]到区间[L,R-1],[L+1,R],[L-1,R],[L,R+1]复杂度低
- 相较与线段树，线段树要求[l,mid],[mid,r]-->[l,r]复杂度较低
- 莫队时间复杂度为O(nlogn)
- 采用的是分块处理查询
- 实现需要注意的点:
- 为了保持原有查询顺序需要保存原序号，根据原序号存储答案
- 区间的移动传入的参数是增加的点和删除的点，不要无脑写
关于该题
- 稍微需要一些数学的变换，记下x,y,z出现的次数分别为a,b,c在区间[l,r],那么概率为C(a,2)+C(b,2)+...C(,2)/C(len,2)
- 变换 a(a-1)+b(b-1).../len(len-1)=(frac{(sum{a^2}-len)}{ len(len-1)})
- 所以需要维护频度的平方和
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=50005;
inline ll sqr(const ll &x){
return x*x;
}
inline ll gcd(const ll &a,const ll &b){
if(!b) return a;
else return gcd(b,a%b);
}
int belong[maxn];//每个点的分块预处理
ll ans1[maxn],ans2[maxn];//存储i次询问的结果
struct Cmd{
int l,r,id;
friend bool operator <(const Cmd &a,const Cmd &b){
if(belong[a.l]==belong[b.l]) return a.r<b.r;
else return belong[a.l]<belong[b.l];
}
}cmds[maxn];
//存储所有询问，因为要将所有询问存储(离线算法)
//所以有时需要非常毒瘤的读入优化
int n,m,c[maxn],sum[maxn];
//c[]存储n个元素
inline void upd(ll &now,int p,int v){
//更新平方和
now-=sqr(sum[c[p]]);
sum[c[p]]+=v;//c[p]的计数
now+=sqr(sum[c[p]]);
//now应该加上改变后的^2-之前^2
//巧妙的避免了讨论
}
inline void solve(){
int L=1,R=0;//[L,R]为当前维护好的区间
ll now=0;//now为当前区间答案
for(int i=1;i<=m;i++){//莫队主要部分
while(L<cmds[i].l){
upd(now,L,-1);L++;//表示L右移动
}
while(L>cmds[i].l){//加上点L-1
upd(now,L-1,1);L--;
}
while(R<cmds[i].r){//加上点R+1
upd(now,R+1,1);R++;
}
while(R>cmds[i].r){
upd(now,R,-1);R--;
}
if(cmds[i].l==cmds[i].r){
ans1[cmds[i].id]=0;
ans2[cmds[i].id]=1;
continue;
}
ans1[cmds[i].id]=now-(cmds[i].r-cmds[i].l+1);
ans2[cmds[i].id]=(ll)(cmds[i].r-cmds[i].l)*(cmds[i].r-cmds[i].l+1);
//printf("db %d %d %lld %lld %lld
",cmds[i].l,cmds[i].r,now,ans1[cmds[i].id],ans2[cmds[i].id]);
ll g=gcd(ans1[cmds[i].id],ans2[cmds[i].id]);
ans1[cmds[i].id]/=g;
ans2[cmds[i].id]/=g;
}
}
int main(){
scanf("%d %d",&n,&m);//n个数,m次询问
int s=sqrt(n);//准备分块
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
belong[i]=((i-1)/s)+1;//每个点分块预处理
}
for(int i=1;i<=m;i++){
scanf("%d %d",&cmds[i].l,&cmds[i].r);
cmds[i].id=i;//需要标号记录原来顺序，因为后面要排序
}
sort(cmds+1,cmds+m+1);//对区间重新排序
solve();
for(int i=1;i<=m;i++){
printf("%lld/%lld
",ans1[i],ans2[i]);
}
return 0;
}