莫隊(duì)：就是一坨軟軟的有彈性的東西Duang~Duang~Duang~

? ? ? ? 為了防止以左端點(diǎn)為第一關(guān)鍵字以右端點(diǎn)為第二關(guān)鍵字使右端點(diǎn)彈來彈去，所以讓左端點(diǎn)所在塊為關(guān)鍵字得到O(n^1.5)的時(shí)間效率，至于分塊的優(yōu)化，根本用不到。

#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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TSHugh/p/7017679.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2038】[国家集训队2010]小Z的袜子 莫队的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。