题目描述
小D举办了元旦联欢活动，其中有一个卡片游戏。
游戏的规则是这样的：有n张卡片，每张卡片上正面写着一个小于等于100的正整数ai，反面都是一样的花色。这n张卡片正面朝下叠成一堆，玩这个游戏的人从中可以抽出连续的k（1≤k≤n）张卡片。如果对于这k张卡片上的数字的平均值a，满足l<=a<=r，那他就可以获得小礼物一件。
小W来玩这个游戏了，她事先通过某些途径知道了这n张卡片上写的数字，现在她想知道她获得小礼物的期望值。
小W对小数很头疼，所以请你用分数的形式告诉她答案。
输入
输入文件名为game.in
输入第1行，三个整数n，l，r。
第2行，包含n个整数ai。
输出
输出文件名为game.out
输出仅1行，表示小W获得小礼物的期望值。输出格式为“P/Q”（P和Q互质）。如果期望值是0或1就不用输出分数了
样例输入
样例输出
提示
【输入输出样例解释1】
【输入输出样例解释1】抽出的卡片 | a（保留2位小数） | 是否满足l<=a<=r |
|
3 | 3.00 | √ |
|
1 | 1.00 | ||
2 | 2.00 | √ |
|
4 | 4.00 | ||
3,1 | 2.00 | √ |
|
1,2 | 1.50 | ||
2,4 | 3.00 | √ |
|
3,1,2 | 2.00 | √ |
|
1,2,4 | 2.33 | √ |
|
3,1,2,4 | 2.50 | √ |
|
【输入输出样例解释2】
由上表得，小W总是可以获得小礼物。因此期望值是1
【数据范围】
对于30%的数据，0<n≤10,000；
对于70%的数据，0<n≤100,000；
对于100%的数据，0<n≤500,000，0<l<r≤100。
由表可得，一共有10种情况，其中有7种情况小W可以获得小礼物。因此小W获得小礼物的期望值是7/10。
这一道题目我刚开始也没有什么头绪。但是一看题解就是恍然大悟的节奏。题解使用的思想相当于片段和思想。你要求的是区间内和处于l,r的个数。经过变形，我们会发现这就是一个求解逆序对，非常的神奇。它就运用到了一些片段和的思想，我们可以直接求解>=l的个数和>r的个数，最后减一减就是在l,r区间内的答案了。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 struct node 10 { 11 long long X,Y; 12 }; 13 14 int N; 15 long long L,R; 16 long long RR[1000005]; 17 node a[1000005]; 18 long long s[1000005]; 19 long long AnsA,AnsB; 20 21 void gbsort1(int l,int r) 22 { 23 int mid=(l+r)/2; 24 if (l == r) return; 25 gbsort1(l,mid); 26 gbsort1(mid+1,r); 27 int head1=l; 28 int tail1=mid; 29 int head2=mid+1; 30 int tail2=r; 31 int len=head1-1; 32 while (head1 <= tail1 && head2 <= tail2) 33 { 34 if (a[head1].X < a[head2].X) 35 { 36 RR[++len]=a[head1].X; 37 head1++; 38 } 39 else if (a[head1].X >= a[head2].X) 40 { 41 RR[++len]=a[head2].X; 42 head2++; 43 AnsA+=(tail1-head1+1); 44 } 45 } 46 while (head1 <= tail1) 47 { 48 RR[++len]=a[head1].X; 49 head1++; 50 } 51 while (head2 <= tail2) 52 { 53 RR[++len]=a[head2].X; 54 head2++; 55 } 56 for (int i=l; i<=r; i++) 57 { 58 a[i].X=RR[i]; 59 } 60 } 61 62 void gbsort2(int l,int r) 63 { 64 int mid=(l+r)/2; 65 if (l == r) return; 66 gbsort2(l,mid); 67 gbsort2(mid+1,r); 68 int head1=l; 69 int tail1=mid; 70 int head2=mid+1; 71 int tail2=r; 72 int len=head1-1; 73 while (head1 <= tail1 && head2 <= tail2) 74 { 75 if (a[head1].Y <= a[head2].Y) 76 { 77 RR[++len]=a[head1].Y; 78 head1++; 79 } 80 else if (a[head1].Y > a[head2].Y) 81 { 82 RR[++len]=a[head2].Y; 83 head2++; 84 AnsB+=(tail1-head1+1); 85 } 86 } 87 while (head1 <= tail1) 88 { 89 RR[++len]=a[head1].Y; 90 head1++; 91 } 92 while (head2 <= tail2) 93 { 94 RR[++len]=a[head2].Y; 95 head2++; 96 } 97 for (int i=l; i<=r; i++) 98 { 99 a[i].Y=RR[i];100 }101 }102 103 long long gcd(long long a,long long b)104 {105 if (b == 0) return a;106 else return gcd(b,a % b);107 }108 109 int main()110 {111 scanf("%d%lld%lld",&N,&L,&R);112 for (int i=1; i<=N; i++)113 {114 int X;115 scanf("%d",&X);116 s[i]=s[i-1]+X;117 a[i].X=L * i - s[i];118 a[i].Y=R * i - s[i];119 }120 AnsA=0; AnsB=0;121 gbsort1(0,N);122 gbsort2(0,N);123 //printf("%lld %lld\n",AnsA,AnsB);124 long long Tmp=(long long) N;125 Tmp=Tmp * (Tmp + 1) / 2;126 long long Ans=AnsA-AnsB;127 if (Ans == Tmp)128 {129 printf("1\n");130 }131 else if (Ans == 0)132 {133 printf("0\n");134 }135 else136 {137 long long D=gcd(Ans,Tmp);138 printf("%lld/%lld\n",Ans/D,Tmp/D);139 }140 return 0;141 }