题意：给一些数，然后每次询问一段区间，问从这个区间中抽走两个数，抽到相同的数的概率
正解：莫队算法
今天新学习了莫队算法，感觉好神，离线的询问好像都可以用莫队。
要不是坑爹的HNOI2016考了两道莫队题，才不得不来入这个坑，A完这道题，就去A掉HNOI2016Day2的两道题。。。
把询问离线下来，然后按照左端点所在块的编号来排序，若在同一个块则以右端点编号排序（有点像分块）
然后我每次暴力处理一下一个询问，之后利用这一次的结果，往前或者往后拓展，把处在同一个块的全部都可以处理掉（期望复杂度：O（1））
最终可以达到O(N^1.5）的复杂度
复杂度证明的话，感觉yy一下可以想得到
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdlib> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 typedef long long LL; 11 const int MAXN = 50011; 12 const int MAXM = 50011; 13 int n,m; 14 int color[MAXN]; 15 LL ans[MAXM]; 16 int siz,zong; 17 LL size[MAXN]; 18 LL num[MAXN]; 19 //莫队算法 20 21 struct wen{ 22 int l,r; 23 int jilu; 24 int k;//存储所在块的编号 25 }Q[MAXM]; 26 27 inline int getint() 28 { 29 int w=0,q=0; 30 char c=getchar(); 31 while((c<'0' || c>'9') && c!='-') c=getchar(); 32 if (c=='-') q=1, c=getchar(); 33 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); 34 return q ? -w : w; 35 } 36 37 bool cmp(wen q,wen qq){ if(q.k==qq.k) return q.r<qq.r; return q.k<qq.k; } 38 //按照左端点所在块的编号来排序，若相等则以右端点编号为序 39 40 inline LL gcd(LL x,LL y) { return y==0? x:gcd(y,x%y); } 41 42 int main() 43 { 44 freopen("hose.in","r",stdin); 45 freopen("hose.out","w",stdout); 46 n=getint();m=getint(); 47 for(int i=1;i<=n;i++) color[i]=getint(); 48 49 zong=sqrt(n); if(zong*zong==n) siz=zong; else siz=n/zong+1; 50 51 for(int i=1;i<=m;i++) { 52 Q[i].l=getint(),Q[i].r=getint(),Q[i].jilu=i,size[i]=Q[i].r-Q[i].l+1; 53 Q[i].k=(Q[i].l-1)/siz+1; 54 } 55 56 sort(Q+1,Q+m+1,cmp); 57 int ljh=1; 58 while(ljh<=m) { 59 int kuai=Q[ljh].k; 60 61 memset(num,0,sizeof(num)); 62 63 for(int j=Q[ljh].l;j<=Q[ljh].r;j++) ans[Q[ljh].jilu]+=2*(num[color[j]]++); 64 ljh++; 65 66 for(;Q[ljh].k==kuai;ljh++) { 67 ans[Q[ljh].jilu]=ans[Q[ljh-1].jilu]; 68 for(int j=Q[ljh-1].r+1 ;j<=Q[ljh].r;j++) ans[Q[ljh].jilu]+=2*(num[color[j]]++); 69 70 if(Q[ljh].l>Q[ljh-1].l) for(int j=Q[ljh-1].l;j<Q[ljh].l;j++) ans[Q[ljh].jilu]-=2*(--num[color[j]]); 71 else for(int j=Q[ljh].l;j<Q[ljh-1].l;j++) ans[Q[ljh].jilu]+=2*(num[color[j]]++); 72 } 73 } 74 75 for(int i=1;i<=m;i++) { 76 LL fenmu; 77 if(size[i]==1) fenmu=1; 78 else fenmu=size[i]*(size[i]-1); 79 LL gong=gcd(fenmu,ans[i]); 80 printf("%lld/%lld ",ans[i]/gong,fenmu/gong); 81 } 82 83 return 0; 84 }