链接:lg1494
题解
- 显然要求的是$\frac {\sum_{i=1}^v{C_{f(i)}^2}}{C_{r-l+1}^2}$ (v表示数字值,f(i)表示数字i在区间内出现的次数)
- 首先考虑分子$C_{x}^2=\frac {x^2-x}{2}$,分子可写成$\frac{\sum_{i=1}^{v}f(i)^2-\sum_{i=1}^{v}f(i)}{2}$
- 显然$\sum_{i=1}^{v}f(i)=r-l+1$
- 现在的问题是已知$[l,r]的值,如何求[l,r+1]的值,这时只增加了一个Z,是很好处理的,设原分子为S_0,现在为S$
- 显然$S=S_0-f(Z)^2+(f(Z)+1)^2-1=S_0+2*f(Z),O(1)即可完成$
- 这样区间间的移动就可以$O(|r-r_i|+|l-l_i|)$做到
- 接下来就可以用莫队完成了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using namespace std;
const int N=1e5+7;
template <typename T>inline void read(T &x){
char c;x=0;int sign=1;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
int n,m,f[N],col[N],pos[N];
ll ans;
struct node{
int l,r,id;
ll a,b;
}q[N];
inline ll gcd(ll a,ll b){
while(b){
ll t=a%b;
a=b;
b=t;
}
return a;
}
inline int cmp_id(node a,node b){return a.id<b.id;}
inline int cmp_pos(node a,node b){return pos[a.l]==pos[b.l]?pos[a.r]<pos[b.r]:pos[a.l]<pos[b.l];}
inline void init(){
read(n);read(m);
rep(i,1,n)read(col[i]);
int x=sqrt(n);
rep(i,1,n)pos[i]=(i-1)/x+1;
rep(i,1,m){read(q[i].l);read(q[i].r);q[i].id=i;}
sort(q+1,q+m+1,cmp_pos);
}
inline void modify(int p,ll &ans,int add){
ans+=2*add*f[col[p]]+1;
f[col[p]]+=add;
}
inline void modify(node &a){
ll t=gcd(a.b,a.a);
if(t){
a.a/=t;
a.b/=t;
}
}
inline void solve(){
int l=1,r=0;ans=0;
rep(i,1,m){
if(r<q[i].r){
for(r=r+1;r<q[i].r;++r)modify(r,ans,1);
modify(r,ans,1);
}
if(q[i].l<l){
for(l=l-1;l>q[i].l;--l)modify(l,ans,1);
modify(l,ans,1);
}
if(r>q[i].r){
for(;r>q[i].r;--r)modify(r,ans,-1);
//modify(r,ans,-1);
}
if(l<q[i].l){
for(;l<q[i].l;++l)modify(l,ans,-1);
//modify(l,ans,-1);
}
if(q[i].l==q[i].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);
modify(q[i]);
}
sort(q+1,q+m+1,cmp_id);
rep(i,1,m)printf("%lld/%lld\n",q[i].a,q[i].b);
}
int main(){
init();
solve();
return 0;
}