前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2038:[2009国家集训队]小Z的袜子(hose)

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

作者头像
用户2965768
发布2019-07-08 17:59:39
3910
发布2019-07-08 17:59:39
举报
文章被收录于专栏:wym

题解:

代码语言:javascript
复制
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 50005;
struct N{int l,r,id;ll A,B;}q[maxn];
int s[maxn],a[maxn],ans,unit;
int Be[maxn];
int cmp(N c,N d){
	return Be[c.l]==Be[d.l]? c.r<d.r: c.l<d.l;
}
int cmp2(N c,N d){
	return c.id<d.id;
}
ll gcd(ll a,ll b){return b>0?gcd(b,a%b):a; }
void revise(int x,int add){ans-=s[a[x]]*s[a[x]]; s[a[x]]+=add; ans+=s[a[x]]*s[a[x]]; }
int main()
{
	int n,m,l,r;
	scanf("%d %d",&n,&m); unit = sqrt(n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),Be[i] = i/unit+1;
	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);
	l = 1,r = 0;
	for(int i=1;i<=m;i++){
		while(l<q[i].l)revise(l,-1),l++;
		while(l>q[i].l)revise(l-1,1),l--;
		while(r<q[i].r)revise(r+1,1),r++;
		while(r>q[i].r)revise(r,-1),r--;
		if(l==r){q[i].A = 0,q[i].B = 1;continue;} 
		q[i].A = ans - (q[i].r-q[i].l+1);
		q[i].B = 1ll*(q[i].r - q[i].l + 1)*(q[i].r - q[i].l);
		ll gd = gcd(q[i].B,q[i].A); q[i].A/=gd;	q[i].B/=gd;
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++){
		printf("%lld/%lld\n",q[i].A,q[i].B);
	}
	
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月04日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档