N,Q<=50000.
若我们已知L~R区间出现的颜色为c1~ck，次数cnt1~cntk 概率表达式？ 若我们已知[L,R]的信息(cnt,P)，我们可以O(1)将它更新为[L+1,R]/[L-1,R]/[L,R-1]/[L,R+1].此即为莫队算法。
我们将询问以[(l-1)/sqrt(N)]为第一关键字，R为第二关键字排序，我们暴力求出第一个询问的答案，然后对于以后的询问答案由之前的询问进行更新 时间复杂度？ 右端点O(N*sqrt(N)) 左端点O(N) 总时间复杂度O(N*sqrt(N))
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define ll long long #define N 50000 using namespace std; int n,m,A[N+5],block; ll ans=0,f[N]; struct query{ int l,r,id,block; }data[N+5]; struct ANs{ ll a,b; }ANS[N]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } bool cmp(query x,query y){ return x.block==y.block? x.r<y.r:x.block<y.block; } void update(int x,int op){ ans-=f[A[x]]*(f[A[x]]-1); f[A[x]]+=op; ans+=f[A[x]]*(f[A[x]]-1); } inline ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y); } int main(){ freopen("a.in","r",stdin); n=read();m=read();block=sqrt(n); for(int i=1;i<=n;++i) A[i]=read(); for(int i=1;i<=m;++i){ data[i].l=read();data[i].r=read();data[i].id=i; data[i].block=(data[i].l-1)/block; } sort(data+1,data+m+1,cmp); int l=1,r=0;//l一定要从1开始，r从0开始 ll a=0,b=0; for(int i=1;i<=m;++i){ for(;l>data[i].l;--l) update(l-1,1); for(;l<data[i].l;++l) update(l,-1); for(;r<data[i].r;++r) update(r+1,1); for(;r>data[i].r;--r) update(r,-1); if(data[i].l==data[i].r){ ANS[data[i].id].a=0; ANS[data[i].id].b=1;continue; } a=ans;b=(ll)(data[i].r-data[i].l+1)*(data[i].r-data[i].l); ll k=gcd(a,b); ANS[data[i].id].a=a/k;ANS[data[i].id].b=b/k; } for(int i=1;i<=m;++i) printf("%lld/%lld\n",ANS[i].a,ANS[i].b); return 0; }