2038: [2009 National Training Team] Small Z socks (hose)

Time Limit: 20 Sec  Memory Limit: 259 MB

Submit: 9894  Solved: 4561

[Submit][Status][Discuss]

Description

As a person with a loose life, Z spends a lot of time each morning trying to find a pair of colorful socks to wear. Finally, one day, Z can no longer bear the annoying process of finding socks, so he decides to leave it to god… Specifically, Z numbered the N socks from 1 to N, and then from L to R. (L Although Z didn’t care whether the socks were a perfect pair, or even whether they were one left and one right, he did care about the color of the socks, after all, wearing two different colors of socks would be awkward. Your task is to tell Z how likely he is to pick two socks of the same color. Of course, Z wants this probability to be as high as possible, so he may ask for more than one (L,R) to make his choice.

Input

The first line of the input file contains two positive integers N and M. N is the number of socks and M is the number of inquiries made by Z. The next line contains N positive integers Ci, where Ci represents the color of the ith sock, and the same color is represented by the same number. The next M lines, each with two positive integers L, R represents a query.

Output

Contains M rows, for each query output score A/B in one row represents the probability of randomly drawing two socks of the same color from the interval [L,R] of that query. If the probability is 0, the output is 0/1, otherwise the output of A/B must be the simplest fraction. (See sample)

Sample Input

6 4 1 2 3 3 3 2 2 1 3 3 5 6\1

Sample Output

2/5 0/1 1/1 4/15 Question 1: C(5,2)=10 possibilities. There are 1 possibilities for picking two 2’s and 3 possibilities for picking two 3’s. The probability is (1+3)/10=4/10=2/5. Question 2: C(3,2)=3 possibilities, unable to pick socks of the same color, the probability is 0/3=0/1. Question 3: C(3,2)=3 possibilities, all of which draw two 3’s, with a probability of 3/3=1/1. Note: the above C(a, b) represents the number of combinations. The number of combinations C(a, b) is equivalent to the number of selection schemes for selecting B out of a different items. [Data scale and convention] N,M ≤ 5000 in 30% of data; N,M ≤ 25000 in 60% of the data; In 100% data, N,M ≤ 50000,1 ≤ L < R ≤ N, Ci ≤ N. \

HINT

Source

Copyright holder: Mo Tao

Title link: www.lydsy.com/JudgeOnline…

Analysis: Mo team algorithm can solve a class of unmodified, offline query problems.

I wrote down a way to do it in segments. Divide 1~n into SQRT (n) segments. Unit = SQRT (n)m Queries are sorted by the number of blocks and then by R. And then we just solve for it.

Learning from kuangbinQAQ

Study notes:

The probability for an interval is the sum/total number of choices for each color of 2 identical choices

So this simplifies to the sum of (the number of colors ^2 – interval length)/ (interval length * interval length minus 1)

The problem becomes quickly finding the sum of the squares of the numbers of each color in an interval

Line segment tree? Each color can be squared separately, but will be stuck

 

That’s why we used the Moot algorithm

 

Scope of use:

The answer of the interval [L,r+1] or [L −1,r] can be obtained in O(1) or O(log2n) after the answer of the interval [L,r] is obtained offline

 

The idea is to find a data structure that can maintain the current answer when inserting and deleting.

So if known [l, r] answer, for l, ‘r’ answer, it is easy to through “| | – l l + | | r – r ‘times for transfer.

As points on the plane, we compute each value in some order, and the cost is the sum of the Manhattan distances. Manhattan distance minimum spanning tree

This is usually done by chunking

 

N Number divided into blocks

Sort by interval, the first keyword is in the block where the left endpoint is, and the second keyword is in the right endpoint.

The complexity analysis looks like this:

1, I and I +1 are in the same block, r is monotonically increasing, so r is O(n). Since there are n^0.5 blocks, this part of the time complexity is n^1.5.

2, I and I +1 span a block, r changes at most N, because there are N ^0.5 blocks, so the time complexity of this part is N ^1.5

3. When I and I +1 are in the same block, L does not change more than N ^0.5, nor does it change more than N ^0.5 across a block. Since there are m queries (the same as N), the time complexity is N ^1.5

So this is order n to the 1.5

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=50050; 5 const int minn=50050; 6 inline int read() 7 { 8 int x=0,f=1; 9 char ch=getchar(); 10 while(ch<'0'||ch>'9') 11 { 12 if(ch=='-') 13 f=-1; 14 ch=getchar(); 15 } 16 while(ch>='0'&&ch<='9') 17 { 18 x=x*10+ch-'0'; 19 ch=getchar(); 20 } 21 return x*f; 22 } 23 inline void write(int x) 24 { 25 if(x<0) 26 { 27 putchar('-'); 28 x=-x; 29 } 30 if(x>9) 31 write(x/10); 32 putchar(x%10+'0'); 33 } 34 struct Query 35 { 36 int L,R,id; 37 }node[maxn]; 39 {40 return b==0? a:gcd(b,a%b); 41 } 42 struct Ans 43 { 44 ll a,b; 46 {47 d= GCD (a,b); 48 a/=d; 49 b/=d; 50 } 51 }ans[maxn]; 52 int a[maxn]; 53 int num[maxn]; 54 int n,m,unit; 55 bool CMP (Query A,Query b)/// divide 1~n into SQRT (n) segments,unit= SQRT (n)m =b.L/unit) 58 return a.L/unit<b.L/unit; 59 else return a.R<b.R; 60 } 61 void work() 62 { 63 ll temp=0; 64 memset(num,false,sizeof(num)); 65 int L=1; 66 int R=0; 67 for(int i=0; i<m; I++) / / / mo algorithm is the core part of 68 {69 while (R < node [I]. R) 70 {71 R++; 72 temp-=(ll)num[a[R]]*num[a[R]]; 73 num[a[R]]++; 74 temp+=(ll)num[a[R]]*num[a[R]]; 75 } 76 while(R>node[i].R) 77 { 78 temp-=(ll)num[a[R]]*num[a[R]]; 79 num[a[R]]--; 80 temp+=(ll)num[a[R]]*num[a[R]]; 81 R--; 82 } 83 while(L<node[i].L) 84 { 85 temp-=(ll)num[a[L]]*num[a[L]]; 86 num[a[L]]--; 87 temp+=(ll)num[a[L]]*num[a[L]]; 88 L++; 89 } 90 while(L>node[i].L) 91 { 92 L--; 93 temp-=(ll)num[a[L]]*num[a[L]]; 94 num[a[L]]++; 95 temp+=(ll)num[a[L]]*num[a[L]]; 96 } 97 ans[node[i].id].a=temp-(R-L+1); 98 ans[node[i].id].b=(ll)(R-L+1)*(R-L); 99 ans[node[i].id].reduce(); 100 } 101 } 102 int main() 103 { 104 //freopen("in.txt","r",stdin); 105 //freopen("out.txt","w",stdout); 106 while(scanf("%d%d",&n,&m)==2) 107 { 108 for(int i=1; i<=n; i++) 109 a[i]=read(); 110 for(int i=0; i<m; i++) 111 { 112 node[i].id=i; 113 node[i].L=read(); 114 node[i].R=read(); 115 } 116 unit=(int)sqrt(n); 117 sort(node,node+m,cmp); 118 work(); 119 for(int i=0; i<m; i++) 120 { 121 printf("%lld/%lld\n",ans[i].a,ans[i].b); 122 } 123 } 124 return 0; 125}Copy the code