二次联通门 : BZOJ 2038: [2009国家集训队]小Z的袜子
/*
BZOJ 2038: [2009国家集训队]小Z的袜子 莫队经典题 但是我并不认为此题适合入门。。 Answer = ∑ C (sum[i], 2) / C (r - l + 1, 2)
= ∑ (sum[i] ^ 2 - sum[i]) / 2 C (r - l + 1, 2) sum表示区间内数i的出现次数 那么∑sum[i]=r-l+1
2*（r-l+1）!
分母= ----------- = （r-l）*（r-l+1）
2!*(r-l-1) ! sum数组随便记录一下就好。。 */
#include <algorithm>
#include <cstdio>
#include <cmath> #define Max 500090 void read (int &now)
{
now = ;
register char word = getchar ();
while (word < '' || word > '')
word = getchar ();
while (word >= '' && word <= '')
{
now = now * + word - '';
word = getchar ();
}
} int belong[Max]; struct Query_Data
{
int l, r; int Id; bool operator < (const Query_Data &now) const
{
return belong[this->l] == belong[now.l] ? this->r < now.r : belong[this->l] < belong[now.l];
}
}; int N, M;
long long Result;
long long count[Max];
int number[Max]; Query_Data query[Max]; inline void Updata (int now, bool type)
{
if (type)
{
Result -= count[number[now]] * count[number[now]];
count[number[now]] ++;
Result += count[number[now]] * count[number[now]];
}
else
{
Result -= count[number[now]] * count[number[now]];
count[number[now]] --;
Result += count[number[now]] * count[number[now]];
}
} long long Get_Gcd (long long a, long long b)
{
return !b ? a : Get_Gcd (b, a % b);
} long long Answer_up[Max], Answer_down[Max]; inline void Calculate (int now)
{
register int l = query[now].l, r = query[now].r;
Answer_up[query[now].Id] = Result - (r - l + );
Answer_down[query[now].Id] = 1ll * (r - l) * (r - l + );
register long long res = Get_Gcd (Answer_up[query[now].Id], Answer_down[query[now].Id]);
Answer_up[query[now].Id] /= res;
Answer_down[query[now].Id] /= res;
} int main (int argc, char *argv[])
{
read (N);
read (M);
int K_Size = sqrt (N);
for (int i = ; i <= N; i ++)
{
belong[i] = (i + ) / K_Size;
read (number[i]);
}
for (int i = ; i <= M; i ++)
{
read (query[i].l);
read (query[i].r);
query[i].Id = i;
}
std :: sort (query + , query + + M); int l = , r = ;
for (int i = ; i <= M; i ++)
{
while (l < query[i].l)
Updata (l ++, false);
while (l > query[i].l)
Updata (-- l, true);
while (r > query[i].r)
Updata (r --, false);
while (r < query[i].r)
Updata (++ r, true);
Calculate (i);
}
for (int i = ; i <= M; i ++)
{
printf ("%lld/", Answer_up[i]);
printf ("%lld\n", Answer_down[i]);
}
//system ("pause");
return ;
}