【bzoj2038】[国家集训队2010]小Z的袜子 莫队

莫队：就是一坨软软的有弹性的东西Duang~Duang~Duang~

        为了防止以左端点为第一关键字以右端点为第二关键字使右端点弹来弹去，所以让左端点所在块为关键字得到O(n^1.5)的时间效率，至于分块的优化，根本用不到。

#include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #define MAXN 50005 using namespace std; typedef long long LL; struct Query {LL l,r,a,b,id; }query[MAXN]; LL pos[MAXN]; int cmp(const Query a,const Query b) {return a.id<b.id; } int comp(const Query a,const Query b) {if(pos[a.l]<pos[b.l])return 1;if(pos[a.l]==pos[b.l]&&a.r<b.r)return 1;return 0; } LL a[MAXN],s[MAXN],n,m,len,l,r,ans; LL gcd(LL x,LL y) {return y==0?x:gcd(y,x%y); } inline void did(LL x,LL di) {ans-=s[a[x]]*s[a[x]];s[a[x]]+=di;ans+=s[a[x]]*s[a[x]]; } inline void work() {for(LL i=1;i<=m;i++){while(l<query[i].l)did(l++,-1);while(l>query[i].l)did(--l,1);while(r<query[i].r)did(++r,1);while(r>query[i].r)did(r--,-1);if(l==r){query[i].a=0;query[i].b=1;continue;}LL son=ans-(r-l+1);LL mo=(LL)(r-l)*(r-l+1);LL k=gcd(son,mo);query[i].a=son/k;query[i].b=mo/k;} } int main() {freopen("hose.in", "r", stdin);freopen("hose.out", "w", stdout);scanf("%lld%lld",&n,&m);len=(LL)(sqrt(n+0.5));l=r=ans=1;for(LL i=1;i<=n;i++){scanf("%lld",&a[i]);pos[i]=(i-1)/len+1;}s[a[1]]++;for(LL i=1;i<=m;i++){scanf("%lld%lld",&query[i].l,&query[i].r);query[i].id=i;}sort(query+1,query+1+m,comp);work();sort(query+1,query+m+1,cmp);for(LL i=1;i<=m;i++)printf("%lld/%lld\n",query[i].a,query[i].b);return 0; }

 

转载于:https://www.cnblogs.com/TSHugh/p/7017679.html

总结

以上是生活随笔为你收集整理的【bzoj2038】[国家集训队2010]小Z的袜子 莫队的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。