首页 > 其他 > 详细

BZOJ2038 [2009国家集训队]小Z的袜子(hose) 莫队

时间:2018-07-21 13:14:41      阅读:216      评论:0      收藏:0      [点我收藏+]

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2038.html

题目传送门 - BZOJ2038

题意

  给定一个数列。长度为 $n$ ,有 $m$ 次询问,每次询问在 区间 $[L,R]$ 中任选两个,问选到相同数的概率为多少,以最简分数形式输出。

  $n,m\leq 50000$

几个字的题解

  莫队裸题 13分钟 1A

  我怎么会来做这种傻逼题

代码

#include <bits/stdc++.h>
using namespace std;
const int N=50005;
int n,m,a[N],tax[N];
struct Query{
	int L,R,id,ans;
}q[N];
bool cmp(Query a,Query b){
	int La=a.L>>8,Lb=b.L>>8;
	if (La!=Lb)
		return La<Lb;
	return a.R<b.R;
}
bool cmpid(Query a,Query b){
	return a.id<b.id;
}
int calc(int x){
	return 1LL*x*(x-1)/2;
}
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=m;i++)
		scanf("%d%d",&q[i].L,&q[i].R),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	memset(tax,0,sizeof tax);
	int L=1,R=0,ans=0;
	for (int i=1;i<=m;i++){
		int Lnow=q[i].L,Rnow=q[i].R;
		while (R<q[i].R)
			ans+=(tax[a[++R]]++);
		while (L>q[i].L)
			ans+=(tax[a[--L]]++);
		while (R>q[i].R)
			ans-=(--tax[a[R--]]);
		while (L<q[i].L)
			ans-=(--tax[a[L++]]);
		q[i].ans=ans;
	}
	sort(q+1,q+m+1,cmpid);
	for (int i=1;i<=m;i++){
		int a=q[i].ans,b=calc(q[i].R-q[i].L+1),g=gcd(a,b);
		printf("%d/%d\n",a/g,b/g);
	}
	return 0;
}

  

BZOJ2038 [2009国家集训队]小Z的袜子(hose) 莫队

原文:https://www.cnblogs.com/zhouzhendong/p/BZOJ2038.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!