维护一个sum即分子,和一个计数用的数组即可O(1)转移
/************************************************************** Problem: 2038 User: walfy Language: C++ Result: Accepted Time:1896 ms Memory:3452 kb****************************************************************/ //#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector #define mod 1000000007#define ld long double#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pli pair #define pii pair #define cd complex #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double eps=1e-6;const int N=50000+10,maxn=20000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; int a[N],belong[N];struct query{ int l,r,id; bool operator <(const query&rhs)const{ if(belong[l]==belong[rhs.l])return r ans[N];void gao(int pos,int op){ if(op==1) { if(co[a[pos]]==0)co[a[pos]]++; else { sum-=co[a[pos]]*(co[a[pos]]-1); co[a[pos]]++; sum+=co[a[pos]]*(co[a[pos]]-1); } } else { if(co[a[pos]]==1)co[a[pos]]--; else { sum-=co[a[pos]]*(co[a[pos]]-1); co[a[pos]]--; sum+=co[a[pos]]*(co[a[pos]]-1); } }}int main(){ int n,m; scanf("%d%d",&n,&m); int block=sqrt(n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); belong[i]=(i-1)/block+1; } for(int i=0;i q[i].l)l--,gao(l,1); while(r q[i].r)gao(r,-1),r--;// printf("%d -----%d %lld\n",l,r,sum);// for(int j=0;j<=n;j++)printf("%d ",co[j]);puts(""); ll fz=sum,fm=1ll*(r-l+1)*(r-l),te=__gcd(fz,fm); if(fm==0) { ans[q[i].id]=mp(0,1); continue; }// printf("%lld %lld %lld\n",fz,fm,te); fz/=te,fm/=te; ans[q[i].id]=mp(fz,fm); } for(int i=0;i