[BZOJ 2038]小Z的袜子
今年第一更……噫
终于学会莫队了，不过目前只能做这样的模板题……
代码：
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <cstdio>#include <cmath>#include <algorithm>#include <utility>using namespace std;const int maxn=50005;typedef long long ll;ll gcd(ll a,ll b){ if(!b){ return a; }else{ return gcd(b,a%b); }}ll C2(ll n){ register ll temp,ns1=n-1; if(n&1){ temp=ns1>>1; return temp*n; }else{ temp=n>>1; return temp*ns1; }} struct Node{ int L_s; int L,R; int id; ll ans1,ans2;};bool cmp1(const Node& a,const Node& b){ if(a.L_s==b.L_s){ return a.R<b.R; }else{ return a.L_s<b.L_s; }}bool cmp2(const Node& a,const Node& b){ return a.id<b.id;}Node Q[maxn];int C[maxn],d[maxn];int n,m;inline void add_p(int x,ll &ans){ d[x]++; ans+=d[x]-1;}inline void sub_p(int x,ll &ans){ d[x]--; ans-=d[x];}inline void Mo(){ register int i,j,L_p,R_p,sqrt_n=sqrt(n+0.5); register ll ans,t_gcd,t2; for(i=1;i<=m;i++){ Q[i].L_s=Q[i].L/sqrt_n; } sort(Q+1,Q+1+m,cmp1); L_p=R_p=Q[1].L; ans=0; d[C[L_p]]++; for(i=1;i<=m;i++){ while(L_p<Q[i].L){ sub_p(C[L_p],ans); L_p++; } while(L_p>Q[i].L){ L_p--; add_p(C[L_p],ans); } while(R_p<Q[i].R){ R_p++; add_p(C[R_p],ans); } while(R_p>Q[i].R){ sub_p(C[R_p],ans); R_p--; } t2=C2(R_p-L_p+1); t_gcd=gcd(ans,t2); Q[i].ans1=ans/t_gcd; Q[i].ans2=t2/t_gcd; } sort(Q+1,Q+1+m,cmp2);} int main(){ register int i; int a,b; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&C[i]); } for(i=1;i<=m;i++){ Q[i].id=i; scanf("%d%d",&a,&b); Q[i].L=a; Q[i].R=b; } Mo(); for(i=1;i<=m;i++){ printf("%lld/%lld\n",Q[i].ans1,Q[i].ans2); } return 0;} |
