F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 2038 >> 求助
WATLE @ 2016-03-03 19:32:30
[ Quote ] [ Edit ] [ Delete ] 1#
对拍无果
求神犇
#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct question
{
int l,r;
int s;
}ques[N];
int size;
bool cmp(question a , question b)
{
int x = a.l/size,y = b.l/size;
if(x != y) return x < y;
return a.r < b.r;
}
int n;
int a[N];
long long ans[N][2];
int block[N];
long long last[N];
long long lastsum;
inline long long gcd(long long a,long long b)
{
if(a==0) return b;
if(b == 0) return a;
return gcd(b,a%b);
}
inline void asks(int lastl,int lastr,int left,int right,int k)
{
// printf("%d %d %d %d %d\n",lastl,lastr,left,right,k);
if(lastr < right)
for(int i = lastr + 1;i <= right;i++)
{
int p = last[a[i]] * last[a[i]];
last[a[i]]++;
lastsum = lastsum - p + last[a[i]] * last[a[i]];
}
else if(lastr > right)
for(int i = right + 1;i <= lastr;i++)
{
int p = last[a[i]] * last[a[i]];
last[a[i]]--;
lastsum = lastsum - p + last[a[i]] * last[a[i]];
}
// printf("lastsum = %d\n",lastsum);
if(lastl < left)
for(int i = lastl;i <= left - 1;i++)
{
int p = last[a[i]] * last[a[i]];
last[a[i]]--;
lastsum = lastsum - p + last[a[i]] * last[a[i]];
}
else if(lastl > left)
for(int i = left;i <= lastl - 1;i++)
{
int p = last[a[i]] * last[a[i]];
last[a[i]]++;
lastsum = lastsum - p + last[a[i]] * last[a[i]];
}
// printf("lastsum = %d\n",lastsum);
long long a,b;
a = lastsum - (right - left + 1);
b = (right - left + 1) * (right - left);
long long p = gcd(a,b);
ans[k][0] = a/p;
ans[k][1] = b/p;
return;
}
int main()
{
int q;
// freopen("a.txt","r",stdin);
// freopen("b2.txt","w",stdout);
memset(last,0,sizeof(last));
scanf("%d%d",&n,&q);
int l = 1,r = sqrt(n);
int p;
for(p = 1;r <= n;p++)
{
l = r + 1;
r = l + sqrt(n) - 1;
}
size = p - 1;
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
for(int i = 0;i < q;i++)
{
scanf("%d%d",&ques[i].l,&ques[i].r);
ques[i].s = i;
}
sort(ques,ques+q,cmp);
l = 1,r = 1;
lastsum = 1;
last[a[1]] = 1;
for(int i = 0;i < q;i++)
{
if(ques[i].l != ques[i].r)
{
asks(l,r,ques[i].l,ques[i].r,ques[i].s);
l = ques[i].l,r = ques[i].r;
}
else
ans[ques[i].s][0] = 0,ans[ques[i].s][1] = 1;
}
for(int i = 0;i < q;i++)
{
printf("%d/",ans[i][0]);
printf("%d\n",ans[i][1]);
}
return 0;
}

_Ann @ 2016-11-08 10:31:15
[ Quote ] [ Edit ] [ Delete ] 2#
Me too...T_T
nzhtl1477 @ 2016-11-08 23:57:16
[ Quote ] [ Edit ] [ Delete ] 3#
无可奉告.jpg
(手动滑稽233)
maoxiangui @ 2018-05-31 18:51:49
[ Quote ] [ Edit ] [ Delete ] 4#
lxl!
[Top] [Previous Page] [Next Page]

HOME Back