Category:莫队
Article From:https://www.cnblogs.com/oi-forever/p/9124671.html

2038: [2009National training team] small Z socks (hose)

Time Limit: 20 Sec  Memory Limit: 259 MB
Submit: 14280  Solved: 6515
[Submit][Status][Discuss]

Description

As a man of undisciplined life, smallZEvery morning it takes a long time to find a pair of clothes from a pile of colorful socks. At last, one day, littleZHe could no longer bear the annoying process of finding socks, so he decided to listen to his fate.……
Specifically, smallZTake thisNOnly socks from1reachNNumber, and then from the numberLreachR(L Although smallZI don’t care whether the two socks are a complete pair or even if the two socks are left right or not, he is very concerned with the color of the socks, after all, wearing two different colors will be embarrassing.
Your task is to tell the littleZ,How much probability does he have to pick up two socks with the same color? Of course, smallZI hope this probability is as high as possible, so he may ask more than one.(L,R)To make it easier for you to choose.

Input

The first line of the input file contains two positive integers N and M. N is the number of socks, and the number of inquiries raised by M for little Z. The next line contains N positive integers Ci, where Ci represents the color of I socks, and the same color is expressed by the same number. Next M line, two positive integers per line L, RExpress an inquiry.

Output

Contains the M row. For each query, the output A/B is expressed in a row, and the probability that the two socks are randomly selected from the interrogation interval [L and R] is the same color. If the probability is 0, output 0/1, otherwise the output A/B must be the simplest fraction. (see the example in detail)

Sample Input

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

Sample Output

2/5
0/1
1/1
4/15
【Example explanation]
Question 1: a total of C (5,2) =10 species are possible, of which two out of 2 have 1 kinds of possibilities, and two 3 out of 3 possibilities, with probability of (1+3) /10=4/10=2/5.
Question 2: a total of C (3,2) =3 species may not be able to draw socks with the same color, with a probability of 0/3=0/1.
Question 3: a total of C (3,2) =3 species may take two out of 3, with a probability of 3/3=1/1.
Note: the above C (a, b) indicates the combination number, and the combination number C (a, b) is equivalent to selecting the number of B alternatives in a different items.
【Data size and agreement
30%In the data, N, M < 5000;
60%In the data, N, M < 25000;
100%For the data, N, M is less than 50000, 1 is less than L &lt, R is less than N, Ci is less than N.
 
Summary: the mod formwork
#include<bits/stdc++.h>

using namespace std;
const int maxn = 100010;
typedef long long ll;

ll n, m, ci[maxn], blo;
ll ans = 0, bl[maxn], sum[maxn];
struct Node{
	ll l, r, ID, A, B;
} q[maxn];
bool cmp(Node a, Node b) {return bl[a.l] == bl[b.l] ?a.r < b.r :a.l < b.l;}
bool CMP(Node a, Node b) {return a.ID < b.ID;}
ll GCD(ll a, ll b) {return b == 0 ?a :GCD(b, a % b);}
ll S(ll x) {return x * x;}
void revise(int x, int sig) {
	ans -= S(sum[ci[x]]); sum[ci[x]] += sig; ans += S(sum[ci[x]]);
}

int main() {
	scanf("%lld%lld", &n, &m); blo = sqrt(n);
	for (int i = 1; i <= n; ++i) scanf("%lld", &ci[i]), bl[i] = i / blo + 1;
	for (int i = 1; i <= m; ++i) {
		scanf("%lld%lld", &q[i].l, &q[i].r); q[i].ID = i;
	}
	sort(q + 1, q + m + 1, cmp);
	ll l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while(l < q[i].l) revise(l++, -1);
		while(l > q[i].l) revise(--l, 1);
		while(r < q[i].r) revise(++r, 1);
		while(r > q[i].r) revise(r--, -1);
		if(q[i].l == q[i].r) {
			q[i].A = 0; q[i].B = 1; continue;
		}
		q[i].A = ans - (q[i].r - q[i].l + 1);
		q[i].B = 1ll * (q[i].r - q[i].l + 1) * (q[i].r - q[i].l);
        ll gcd = GCD(q[i].A, q[i].B); q[i].A /= gcd; q[i].B /= gcd;
	} sort(q + 1, q + m + 1, CMP);
	for (int i = 1; i <= m; ++i) printf("%lld/%lld\n", q[i].A, q[i].B);
	return 0;
}

  

Leave a Reply

Your email address will not be published. Required fields are marked *