\u4ee4\u989c\u8272\u4e3a\\(c_i\\)\u4e3a\u7b2c\\(i\\)\u79cd\u989c\u8272\u5728\u7ed9\u5b9a\u533a\u95f4\u5185\u51fa\u73b0\u7684\u6b21\u6570\u3002
\u5219\uff0c\u9898\u76ee\u6240\u6c42\u4e3a\uff1a
$$\\frac{\\sum_{i=1}^{n}c_{i}(c_{i}-1)}{(r-l)(r-l+1)}$$
\u5c55\u5f00\u53ef\u4ee5\u5f97\u5230\uff1a
$$\\frac{\\sum_{i=1}^{n}c_{i}^2-\\sum_{i=1}^{n}c_{i}}{(r-l)(r-l+1)}$$
\u7531\u6027\u8d28\u53ef\u5f97\uff1a
$$\\sum_{i=1}^{n}c_{i}=r-l+1$$
\u6545\u800c\uff0c\u6211\u4eec\u9700\u8981\u6c42\u7684\u4ec5\u6709\uff1a
$$\\sum_{i=1}^{n}c_{i}^2$$
\u5bf9\u4e8e\u8fd9\u4e2a\u5f0f\u5b50\u7684\u6c42\u6cd5\uff0c\u6211\u4eec\u5f88\u5bb9\u6613\u53ef\u4ee5\u60f3\u5230\u83ab\u961f\u3002
\u6211\u4eec\u8003\u8651\u4e00\u4e2a\u533a\u95f4\u6dfb\u52a0\u4e0a\u4e00\u4e2a\u6570\u4e0e\u5220\u9664\u4e00\u4e2a\u6570\u9020\u6210\u7684\u5f71\u54cd\u3002
\u4ee4\u4fee\u6539\u7684\u989c\u8272\u4e3a\\(x\\)\uff0c\u5219\uff1a
$$\\Delta v=\\sum_{i=1}^{n}c_{i}^2-c_{x}^{2}+(c_{x}\u00b11)^2-\\sum_{i=1}^{n}c_{i}^2$$
\u5c55\u5f00\u53ef\u5f97\uff1a
$$\\Delta v=1\u00b12c_{x}$$<\/p>\n\n\n\n
\u4e0b\u9762\u8003\u8651\u83ab\u961f\u3002
\u83ab\u961f\u7684\u539f\u7406\u5927\u81f4\u662f\uff0c\u5c06\u539f\u6570\u5217\u5206\u5757\uff0c\u7136\u540e\u5c06\u8be2\u95ee\u4ee5\u5de6\u7aef\u70b9\u5728\u539f\u6570\u5217\u4e2d\u7684\u5757\u4e3a\u7b2c\u4e00\u5173\u952e\u5b57\uff0c\u53f3\u7aef\u70b9\u4e3a\u7b2c\u4e8c\u5173\u952e\u8bcd\u6765\u6392\u5e8f\u3002
\u867d\u7136\u8bf4\u5b83\u662f\u4e00\u79cd\u4f18\u5316\u540e\u7684\u66b4\u529b\uff0c\u4f46\u662f\uff0c\u82e5\u4ee4\u4e00\u6b21\u4fee\u6539\u7684\u590d\u6742\u5ea6\u662f\\(f_{n}\\)\uff0c\u6839\u636e\u6700\u5c0f\u76f4\u7ebf\u65af\u5766\u7eb3\u6811\u7684\u6027\u8d28\uff0c\u53ef\u4ee5\u8bc1\u660e\u8fd9\u4e48\u505a\u7684\u590d\u6742\u5ea6\u662f \\(O(f_{n} n \\sqrt{m})\\)\uff0c\u53ef\u4ee5\u901a\u8fc7\u6b64\u9898\u3002
\u4f9d\u636e\u6bd2\u7624lxl\u7684\u8bf4\u6cd5\uff0c\u83ab\u961f\u6700\u5feb\u7684\u5206\u5757\u5927\u5c0f\u662f\\(n\/\\sqrt{m*2\/3}\\)
\u6545\u800c\u6211\u4eec\u5bf9\u539f\u6570\u5217\u5206\u5757\u5b8c\u4ee5\u540e\uff0c\u5c06\u8be2\u95ee\u6392\u5e8f\u3002\u7136\u540e\u5f00\u59cb\u79fb\u52a8\u533a\u95f4\u3002
\u626b\u4e00\u904d\u5373\u53ef\u3002
\u53e6\u5916\u5c31\u662f\u4e00\u4e2a\u5c0f\u4f18\u5316\uff0c\u6392\u5e8f\u7684\u65f6\u5019\u5206\u5947\u5076\u6392\u5e8f\uff0c\u4e5f\u5c31\u662f\u8bf4\uff0c\u5947\u6570\u5757\u53f3\u7aef\u70b9\u9012\u589e\uff0c\u5076\u6570\u5757\u53f3\u7aef\u70b9\u9012\u51cf\u3002
\u539f\u7406\u5f88\u7b80\u5355\uff0c\u5c31\u662f\u79fb\u8fc7\u53bb\u518d\u79fb\u56de\u6765\uff0c\u8def\u4e0a\u7684\u70b9\u90fd\u626b\u4e86\u4e00\u904d\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<algorithm>\n#include<cmath>\nint BLOCK;\nint belong[50005];\nstruct Query{\n\tint l;\n\tint r;\n\tint id;\n\tint len;\n\tinline bool operator <(const Query &B)const{\n\t\treturn (belong[l]^belong[B.l])?(belong[l]<belong[B.l]):((belong[l]&1)?r<B.r:r>B.r);\n\t}\n}q[50005];\nlong long tot=0;\nint cnt[50005];\ninline void add(int X){\n\ttot+=(cnt[X]<<1|1);\n\t++cnt[X];\n}\ninline void del(int X){\n\ttot+=(1-(cnt[X]<<1));\n\t--cnt[X];\n}\ninline long long Gcd(long long A,long long B){\n\treturn B?Gcd(B,A%B):A;\n}\nlong long ans1[50005],ans2[50005];\nint n,m,a[50005];\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tBLOCK=n\/std::sqrt(m*2.0\/3.0); \n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",a+i);\n\t}\n\tfor(int i=1;i<=m;++i){\n\t\tscanf(\"%d%d\",&q[i].l,&q[i].r);\n\t\tq[i].id=i;\n\t\tq[i].len=q[i].r-q[i].l+1;\n\t\tans2[i]=1;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tbelong[i]=(i-1)\/BLOCK+1;\n\t}\n\tstd::stable_sort(q+1,q+1+m);\n\tint l=q[1].l,r=q[1].l-1;\n\tlong long nwgcd;\n\tfor(int i=1;i<=m;++i){\n\t\twhile(l<q[i].l){\n\t\t\tdel(a[l]);\n\t\t\t++l;\n\t\t}\n\t\twhile(l>q[i].l){\n\t\t\t--l;\n\t\t\tadd(a[l]);\n\t\t}\n\t\twhile(r>q[i].r){\n\t\t\tdel(a[r]);\n\t\t\t--r;\n\t\t}\n\t\twhile(r<q[i].r){\n\t\t\t++r;\n\t\t\tadd(a[r]);\n\t\t}\n\t\tif(tot!=q[i].len){\n\t\t\tans1[q[i].id]=tot-q[i].len,ans2[q[i].id]=1LL*(q[i].r-q[i].l)*q[i].len;\n\t\t\tnwgcd=Gcd(ans1[q[i].id],ans2[q[i].id]);\n\t\t\tans1[q[i].id]\/=nwgcd,ans2[q[i].id]\/=nwgcd;\n\t\t}\n\t}\n\tfor(int i=1;i<=m;++i){\n\t\tprintf(\"%lld\/%lld\\n\",ans1[i],ans2[i]);\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4ee4\u989c\u8272\u4e3a\\(c_i\\)\u4e3a\u7b2c\\(i\\)\u79cd\u989c\u8272\u5728\u7ed9\u5b9a\u533a\u95f4\u5185\u51fa\u73b0\u7684\u6b21\u6570\u3002 \u5219\uff0c\u9898\u76ee\u6240\u6c42\u4e3a\uff1a $$\\frac{\\sum … <\/p>\n