題目大意

有\(n\)(\(n\leq5*10^4\))個數\(a_1,a_2,...,a_n\)(\(\forall i\in[1,n], 1\leq a_i\leq n\))
\(m\)(\(m\leq5*10^4\))次詢問，每次給出區間\([L,R]\)，求在\(a_L,a_{L+1},...,a_R\)中隨機選兩個數，兩數相等的概率

題解

設區間\([L,R]\)中，值為\(i\)的數的個數為\(b_i\)
那么答案就是\(\sum_{i=1}^{n}{C_{b_i}^{2}}\)
發現將區間變成\([L+1,R],[L,R+1],[L-1,R],[L,R-1]\)時，維護\(b\)數組的復雜度是\(\Theta(1)\)的
這樣就可以用莫隊離線解決了

代碼

#include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<iomanip> #include<iostream> #include<map> #include<queue> #include<set> #include<stack> #include<vector> #define rep(i,x,y) for(register int i=(x);i<=(y);++i) #define dwn(i,x,y) for(register int i=(x);i>=(y);--i) #define maxn 50010 #define blo 223 #define LL long long using namespace std; int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } void write(LL x) {if(x==0){putchar('0');return;}int f=0;char ch[20];if(x<0)putchar('-'),x=-x;while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);return; } struct que{int l,r,id;}q[maxn]; int nowl,nowr,num[maxn],n,m,a[maxn]; LL ansa[maxn],ansb[maxn],nowans; LL gcd(LL a,LL b) {if(a>b)swap(a,b);if(!a)return b;return gcd(b%a,a); } bool cmpl(que x,que y){return x.l<y.l;} bool cmpr1(que x,que y){return x.r<y.r;} bool cmpr2(que x,que y){return x.r>y.r;} LL c2(int x){return (LL)x*(LL)(x-1)/2ll;} int main() {n=read(),m=read();rep(i,1,n)a[i]=read();rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;sort(q+1,q+m+1,cmpl);for(int i=1,s=1,t=1+blo;s<=m;s=t+1,t=s+blo,i){int lim=min(t,m);if(i&1)sort(q+s,q+lim+1,cmpr1);else sort(q+s,q+lim+1,cmpr2);}nowl=1,nowr=0;rep(i,1,m){while(nowr<q[i].r)nowr++,nowans-=c2(num[a[nowr]]),num[a[nowr]]++,nowans+=c2(num[a[nowr]]);while(nowl>q[i].l)nowl--,nowans-=c2(num[a[nowl]]),num[a[nowl]]++,nowans+=c2(num[a[nowl]]);while(nowr>q[i].r)nowans-=c2(num[a[nowr]]),num[a[nowr]]--,nowans+=c2(num[a[nowr]]),nowr--;while(nowl<q[i].l)nowans-=c2(num[a[nowl]]),num[a[nowl]]--,nowans+=c2(num[a[nowl]]),nowl++;if(nowans==0)ansa[q[i].id]=0,ansb[q[i].id]=1;else{ansa[q[i].id]=nowans,ansb[q[i].id]=c2(q[i].r-q[i].l+1);LL gdc=gcd(ansa[q[i].id],ansb[q[i].id]);ansa[q[i].id]/=gdc,ansb[q[i].id]/=gdc;}}rep(i,1,m)write(ansa[i]),putchar('/'),write(ansb[i]),putchar('\n');return 0; }

轉載于:https://www.cnblogs.com/xzyf/p/10391449.html

總結

以上是生活随笔為你收集整理的并不对劲的bzoj2038:p1494:[国家集训队]小Z的袜子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。