如何建设学校的微网站首页,多用户电商平台,学校网站建设哪家好,wordpress页面顶部正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1494 题目大意
区间任意取两个数#xff0c;求取到相同的数的概率。 解题思路
假设一个区间有x个y#xff0c;那么两个都取到y的方案数是x∗(x−1)x*(x-1)x∗(x−1)#xff0c;那么取到相同总共方…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1494 题目大意
区间任意取两个数求取到相同的数的概率。 解题思路
假设一个区间有x个y那么两个都取到y的方案数是x∗(x−1)x*(x-1)x∗(x−1)那么取到相同总共方案数∑i1nxi∗(xi−1)\sum_{i1}^nx_i*(x_i-1)∑i1nxi∗(xi−1)。总共取的方案数(r−l1)∗(r−l)(r-l1)*(r-l)(r−l1)∗(r−l)答案就是 ∑i1nxi∗(xi−1)(r−l1)∗(r−l)\frac{\sum_{i1}^nx_i*(x_i-1)}{(r-l1)*(r-l)}(r−l1)∗(r−l)∑i1nxi∗(xi−1) 对于每个xix_ixi直接莫队就好了。 不过莫队要用分块优化一下 code
#includecstdio
#includecmath
#includealgorithm
#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]11) return x.ry.r;else return x.ry.r; }else return id[x.l]id[y.l];
}//分块优化莫队——排序
inline void add(ll x)//加一个数
{cnt[x];if(cnt[x]1)nowcnt[x]*(cnt[x]-1)-(cnt[x]-1)*(cnt[x]-2);
}
inline void del(ll x)//去掉一个数
{cnt[x]--;if(cnt[x]0)nowcnt[x]*(cnt[x]-1)-(cnt[x]1)*cnt[x];
}
void get_ans(ll x,ll y,ll id)//计算答案
{if(!x)y1;else{ll d__gcd(x,y);x/d;y/d;}ans[id].xx;ans[id].yy;
}
int main()
{freopen(testdata.in,r,stdin);freopen(data.out,w,stdout);scanf(%lld%lld,n,m);tsqrt(n);for(ll i1;in;i)scanf(%lld,w[i]),id[i](i-1)/t1;for(ll i1;im;i)scanf(%lld%lld,a[i].l,a[i].r),a[i].idi;sort(a1,a1m,cmp);la[1].l;ra[1].r;for(ll il;ir;i)add(w[i]);get_ans(now,(r-l1)*(r-l),a[1].id);for(ll i2;im;i){while(la[i].l) del(w[l]);while(la[i].l) add(w[--l]);while(ra[i].r) add(w[r]);while(ra[i].r) del(w[r--]);//边框移动get_ans(now,(r-l1)*(r-l),a[i].id);}for(ll i1;im;i)printf(%lld/%lld\n,ans[i].x,ans[i].y);
}
