Codevs3324 新斯诺克

题目描述 Description

斯诺克又称英式台球，是一种流行的台球运动。在球桌上，台面四角以及两长边中心位置各有一个球洞，使用的球分别为1 个白球，15 个红球和6 个彩球（黄、绿、棕、蓝、粉红、黑）共22个球。

击球顺序为一个红球、一个彩球直到红球全部落袋，然后以黄、绿、棕、蓝、粉红、黑的顺序逐个击球，最后以得分高者为胜。斯诺克的魅力还在于可以打防守球，可以制造一些障碍球使对方无法击打目标球而被扣分。正是因为这样，斯诺克是一项充满神奇的运动。

现在考虑这样一种新斯诺克，设母球（母球即是白球，用于击打其他球）的标号为M，台面上有N 个红球排成一排，每一个红球都有一个标号，他们的标号代表了他们的分数。

现在用母球击打这些红球，一杆击打，如果母球接触到红球，就称为“K 到红球”。我们假设，一次可以击打任意多相邻连续的红球，也可以只击打一个球。并且红球既不会落袋，也不会相互发生碰撞，而只是停留在原处。每次击打时候，要想“K 到红球”，至少要击打一个红球，如果想一次击打多个红球，那么击打的红球必须是依次连续排列的。如果一次“K 到红球”所有红球的标号之和的平均数大于母球的标号M，就获得了一个“连击”。

现在请你计算总共能有多少种“连击”方案。

注意：如果当前有标号为1、2、3 的三种红球，母球标号为0，有如下6 种获得“连击”方案：（ 1）、（ 2）、（ 3）、（ 1，2）、（ 2，3）、（ 1，2，3）

输入描述 Input Description

共有两行。

第一行是N，M (N<=100000，M<=10000) ，N 表示台面上一共有N 个红球，M 表示母球的标号。

第二行是N 个正整数，依次表示台面上N 个红球的标号，所有标号均不超过10000。

输出描述 Output Description

只有一个数，为“连击”的方案总数。

样例输入 Sample Input

4 3

3 7 2 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

请看上面。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int n,m;
 6 long long ans;
 7 int f[100001],tmp[100001];
 8 
 9 int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 
17 void  merge(int left,int mid,int right)
18 {
19     int i=left,j=mid+1,k=left;
20     while(i<=mid&&j<=right)
21     {
22         if(f[i]<f[j])
23         {
24             tmp[k++]=f[i++];
25             ans+=right-j+1;
26         }
27         else
28         {
29             tmp[k++]=f[j++];
30         }
31     }
32     while(i<=mid) tmp[k++]=f[i++];
33     while(j<=right) tmp[k++]=f[j++];
34     for(int i=left;i<=right;i++)
35         f[i]=tmp[i];
36 }
37 
38 void Mergesort(int left,int right)
39 {
40     if(left==right) return;
41     int mid=(left+right)/2;
42     Mergesort(left,mid);
43     Mergesort(mid+1,right);
44     merge(left,mid,right);
45 }
46 
47 int main()
48 {
49     n=read();m=read();
50     for(int i=1;i<=n;i++)
51     {
52         f[i]=read()-m+f[i-1];
53     }
54     Mergesort(0,n);//注意0
55     cout<<ans<<endl;
56     return 0;
57 }

树状数组：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 long long ans;
 8 int a[100001];
 9 
10 struct NODE
11 {
12     int val,pos;
13 }node[100001];
14 int c[100001];
15 
16 int read()
17 {
18     int x=0,f=1;char ch=getchar();
19     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
20     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
21     return x*f;
22 }
23 
24 bool cmp(NODE a,NODE b)
25 {
26     if(a.val!=b.val)
27         return a.val<b.val;//<求正序对,>求逆序对
28     else return a.pos>b.pos;
29 }
30 
31 int lowbit(int x)
32 {
33     return x&(-x);
34 }
35 
36 void update(int x,int num)
37 {
38     while(x<=n+1)
39     {
40         c[x]+=num;
41         x+=lowbit(x);
42     }
43 }
44 
45 int sum(int x)
46 {
47     int sum=0;
48     while(x>0)
49     {
50         sum+=c[x];
51         x-=lowbit(x);
52     }
53     return sum;
54 }
55 
56 int main()
57 {
58     n=read();m=read();
59     node[1]=(NODE){0,1};
60     for(int i=2;i<=n+1;i++)
61     {
62         a[i]=a[i-1]+read()-m;
63         node[i].val=a[i];
64         node[i].pos=i;
65     }
66     sort(node+1,node+n+2,cmp);
67     for(int i=1;i<=n+1;i++)
68     {
69         ans+=sum(node[i].pos);
70         update(node[i].pos,1);
71     }
72     cout<<ans<<endl;
73     return 0;
74 }