正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1494

---

題目大意

區(qū)間任意取兩個數(shù)，求取到相同的數(shù)的概率。

---

解題思路

假設(shè)一個區(qū)間有x個y，那么兩個都取到y(tǒng)的方案數(shù)是$x?(x?1)$，那么取到相同總共方案數(shù)${\sum }_{i=1}^n{x}_i?(x_i?1)$。總共取的方案數(shù)$(r?l+1)?(r?l)$，答案就是
$$\frac{{\sum }_{i=1}^n{x}_i?(x_i?1)}{(r?l+1)?(r?l)}$$
對于每個$x_i$，直接莫隊就好了。
不過莫隊要用分塊優(yōu)化一下

---

code

#include<cstdio> #include<cmath> #include<algorithm> #define N 50010 #define ll long long using namespace std; struct node{ll l,r,id; }a[N]; struct ans_node{ll x,y; }ans[N]; ll n,m,w[N],l,r,now,id[N],t; ll cnt[N]; inline bool cmp(node x,node y){if (id[x.l]==id[y.l]){if (id[x.l]&1==1) return x.r<y.r;else return x.r>y.r; }else return id[x.l]<id[y.l]; }//分塊優(yōu)化莫隊——排序 inline void add(ll x)//加一個數(shù) {cnt[x]++;if(cnt[x]>1)now+=cnt[x]*(cnt[x]-1)-(cnt[x]-1)*(cnt[x]-2); } inline void del(ll x)//去掉一個數(shù) {cnt[x]--;if(cnt[x]>0)now+=cnt[x]*(cnt[x]-1)-(cnt[x]+1)*cnt[x]; } void get_ans(ll x,ll y,ll id)//計算答案 {if(!x)y=1;else{ll d=__gcd(x,y);x/=d;y/=d;}ans[id].x=x;ans[id].y=y; } int main() {freopen("testdata.in","r",stdin);freopen("data.out","w",stdout);scanf("%lld%lld",&n,&m);t=sqrt(n);for(ll i=1;i<=n;i++)scanf("%lld",&w[i]),id[i]=(i-1)/t+1;for(ll i=1;i<=m;i++)scanf("%lld%lld",&a[i].l,&a[i].r),a[i].id=i;sort(a+1,a+1+m,cmp);l=a[1].l;r=a[1].r;for(ll i=l;i<=r;i++)add(w[i]);get_ans(now,(r-l+1)*(r-l),a[1].id);for(ll i=2;i<=m;i++){while(l<a[i].l) del(w[l++]);while(l>a[i].l) add(w[--l]);while(r<a[i].r) add(w[++r]);while(r>a[i].r) del(w[r--]);//邊框移動get_ans(now,(r-l+1)*(r-l),a[i].id);}for(ll i=1;i<=m;i++)printf("%lld/%lld\n",ans[i].x,ans[i].y); }

總結(jié)

以上是生活随笔為你收集整理的P1494-[国家集训队]小Z的袜子【分块优化莫队】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。