专栏首页wym2038:[2009国家集训队]小Z的袜子(hose)

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

题解:

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • 区间更新与点值

    用户2965768
  • HDU5036 Explosion(期望 bitset)

    首先根据期望的线性性,可以转化为求每个点的期望打开次数,又因为每个点最多会被打开一次,只要算每个点被打开的概率就行了

    attack
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • Topcoder SRM 698 Div1 250 RepeatString(dp)

    attack
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack

扫码关注云+社区

领取腾讯云代金券