题意：（转）……
题解：莫队算法 分块乱搞
参考资料 ：
代码：
/**************************************************************Problem: 2038User: alpc_wtLanguage: C++Result: AcceptedTime:1176 msMemory:3244 kb****************************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;typedef long long ll;const int N = 50000 + 10;int n,m,block;ll ans = 0;ll gcd(ll a,ll b){return a%b==0 ? b : gcd(b,a%b);}struct answer{int l,r,id;ll a,b;}p[N];int pos[N],col[N],s[N];int cmp(answer a,answer b){if(pos[a.l] == pos[b.l]) return a.r < b.r;return a.l < b.l;}int cmp2(answer a,answer b){return a.id < b.id;}void update(int q,int x){ans -= s[col[q]]*s[col[q]];s[col[q]] += x;ans += s[col[q]]*s[col[q]];}void solve(){int l,r;for(int i=1,l=1,r=0;i<=m;i++){//按块进行更新for(;r<p[i].r;r++)update(r+1,1);for(;r>p[i].r;r–)update(r,-1);for(;l<p[i].l;l++)update(l,-1);for(;l>p[i].l;l–)update(l-1,1);p[i].a = ans – (p[i].r – p[i].l + 1);p[i].b = (ll)(p[i].r – p[i].l + 1)*(p[i].r – p[i].l);if(p[i].a==0 || p[i].l==p[i].r){p[i].a = 0;p[i].b = 1;continue;}ll gg = gcd(p[i].a,p[i].b);p[i].a /= gg;p[i].b /= gg;}}int main(){memset(s,0,sizeof(s));scanf("%d%d",&n,&m);block = (int)sqrt(n);for(int i=1;i<=n;i++) pos[i] = i/block + 1;for(int i=1;i<=n;i++) scanf("%d",&col[i]);for(int i=1;i<=m;i++){scanf("%d%d",&p[i].l,&p[i].r);p[i].id = i;}sort(p+1,p+1+m,cmp);solve();sort(p+1,p+1+m,cmp2);for(int i=1;i<=m;i++)printf("%lld/%lld\n",p[i].a,p[i].b);return 0;}
，生活中若没有朋友，就像生活中没有阳光一样
