首页 > > 程序设计 > C/C++ >

bzoj2038 [ 2009国家集训队 ] -- 莫队

2018-06-17 23:16:58来源：未知阅读 ()

莫队模板题。转移时O(1)维护一下总方案数与相同颜色方案数就可以了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define N 50010
 8 #define ll long long
 9 struct Node{
10     int l,r,f,F;
11 }b[N];
12 int a[N],c[N],i,j,n,l,r,s,m;
13 ll S[2],Ans[N][2],g;
14 inline bool Cmp(Node a,Node b){
15     return a.f<b.f||(a.f==b.f&&a.r<b.r);
16 }
17 inline void Up(int x){
18     S[0]+=c[x]++;S[1]++;
19 }
20 inline void Down(int x){
21     S[0]-=--c[x];S[1]--;
22 }
23 inline void Work(int x){
24     Ans[x][0]=S[0];Ans[x][1]=S[1]*(S[1]-1)>>1;
25 }
26 inline ll Gcd(ll x,ll y){return !y?x:Gcd(y,x%y);}
27 int main()
28 {
29     scanf("%d%d",&n,&m);
30     s=sqrt((double)n);
31     for(i=1;i<=n;i++)scanf("%d",&a[i]);
32     for(i=1;i<=m;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].f=(b[i].l-1)/s+1,b[i].F=i;
33     sort(b+1,b+m+1,Cmp);
34     for(i=l=1,r=0;i<=m;i++){
35         while(b[i].l<l)Up(a[--l]);
36         while(b[i].r>r)Up(a[++r]);
37         while(b[i].l>l)Down(a[l++]);
38         while(b[i].r<r)Down(a[r--]);
39         Work(b[i].F);
40     }
41     for(i=1;i<=m;i++)
42     if(!Ans[i][0])printf("0/1\n");else{
43         g=Gcd(Ans[i][0],Ans[i][1]);
44         printf("%lld/%lld\n",Ans[i][0]/g,Ans[i][1]/g);
45     }
46     return 0;
47 }