# POJ PKU 1990 MooFest 解题报告

OK，贴代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXN 20005
class cow
{
public:
int v;
int pos;
cow(){};
~cow(){};
};

bool cmp(cow a,cow b)
{
return a.v < b.v;
}
cow cw[MAXN];
long long belowXNT[MAXN];//树状数组，保存小于等于某坐标的牛的个数,计算时使用
long long belowXN[MAXN];//一般数组，保存小于等于某坐标和索引的牛的个数
long long velowXRT[MAXN];//树状数组，保存索引小于等于某的牛且坐标也小于它的牛的坐标之和,计算时使用
long long velowXR[MAXN];//一般数组，保存索引小于等于某的牛且坐标也小于它的牛的坐标之和
long long velowXRA[MAXN];//一般数组，保存小于等于某牛的坐标之和

int lowbit(int t)
{
return t&(t^(t-1));
}
void setVal(int pos, int num, long long treeG[], int maxn)
{
while (pos <= maxn)
{
treeG[pos] += num;
pos += lowbit(pos);
}
}
long long getSum(int pos, long long treeG[])
{
long long sum = 0;
while (pos > 0)
{
sum += treeG[pos];
pos -= lowbit(pos);
}
return sum;
}

int main()
{
int i,n;
long long output = 0;
memset(belowXN, 0, sizeof(belowXN));
memset(belowXNT, 0, sizeof(belowXN));
memset(velowXR, 0, sizeof(velowXR));
memset(velowXRA, 0, sizeof(velowXRA));
memset(velowXRT, 0, sizeof(velowXRT));
scanf("%d",&n);
for(i = 0 ; i < n ; i ++)
scanf("%d %d", &cw[i].v, &cw[i].pos);

sort(cw, cw + n, cmp);
for(i = 0 ; i < n ; i ++)
{
velowXRA[i] = velowXRA[i - 1] + cw[i].pos;
setVal(cw[i].pos, 1, belowXNT, MAXN);
setVal(cw[i].pos, cw[i].pos, velowXRT, MAXN);
velowXR[i] = getSum(cw[i].pos, velowXRT);
belowXN[i] = getSum(cw[i].pos, belowXNT);
}

for(i = 1 ; i < n ; i ++)
//output += cw[i].v * ((belowXN[i] - 1) * cw[i].pos - velowXR[i] + cw[i].pos + velowXRA[i] - velowXR[i] - (i - belowXN[i] + 1) * cw[i].pos);
output += cw[i].v * ((belowXN[i] - i + belowXN[i] - 1 ) * cw[i].pos - 2 * velowXR[i] + velowXRA[i]);//这里是上面式子的简化版

printf("%lld\n",output);
return 0;
}```

167 篇文章28 人订阅

0 条评论

## 相关文章

12340

13330

284100

17730

36160

### 数控宏程序的编程及应用

1. 什么场合会用到宏程序编程？ 其实说起来宏就是用公式来加工零件，比如说椭圆，如果没有宏的话，我们要逐点算出曲线上的点，然后慢慢来用直线逼近，如果是个光洁度要...

21880

11040

32010

29640

36050