树状数组相关应用之二元问题

一维数组处理二元问题

此类问题的处理方法一般采用定一议二
POJ—1900：Moofest
树状数组相关应用之二元问题

思路: 树状数组

分析:

1 题目给定n头牛的听力v[i]. 现在规定两头你i和j如果要进行交流的话那么消耗的能量就是dis(i,j)max(v[i].v[j])，现在问n头牛总共的n(n-1)*2种方式消耗的总的能量

2 题目要求的是所有的牛的交流方式的总的消耗能量

看这个样例

3 1

2 5

2 6

4 3

那么所有的区间为[1.3],[1,5],[1,6],[3,5],[3,6],[5,6]

那么总和为4dis[1.3]+3dis[1,5]+3dis[1,6]+4dis[3,5]+4dis[3,6]+2dis[5,6] = 4*(dis[1.3]+dis[3,5]+dis[3,6])+3*(dis[1,5]+dis[1,6])+2*(dis[5,6]);

那么题目要求的ans = ∑(v[i]*(所有比v[i]小的牛的坐标的总和))

3 那么我们来分解这个式子，我们对点按照音量的值从小到大排完序之后

那么对于任一的一点i，i之前的牛的音量值肯定小于v[i]，但是坐标的值可能比x[i]大也可能比x[i]小，因此我们应该分成两部分来考虑，就是坐标是i的左边和右边

首先考虑左边的情况，假设左边比小于等于v[i]的牛有三头坐标分别为a b c，那么左边的值就是v[i](x[i]-a)+v[i](x[i]-b)+v[i](x[i]-c) => v[i](3*x[i]-(a+b+c))

那么我们假设左边小于v[i]的牛有countLeft头，总的坐标为totalLeft，那么左边的值为v[i](countLeftx[i]-totalLeft);

接下来考虑右边的情况，由于我们已经按照v的值排序，那么我们能够很好的计算出小于等于v[i]的音量值的总的坐标之后，我们设为totalDis，那么根据左边求出的小于等于v[i]的个数为countLeft，那么右边的个数为i-countLeft，那么同理右边的坐标之和为totalDis-totalLeft , 那么右边的值为v[i]*(totalDis-totalLeft-(i-countLeft)*x[i]);

那么对于排序后的第i头牛来说比它小的音量的牛的值为v[i](countLeftx[i]-totalLeft)+v[i]*(totalDis-totalLeft-(i-countLeft)*x[i]);
4 我们已经知道了公式，现在我们只要去求countLeft和totalLeft即可，由于我们已经按照v的值排序，那么我们只要对坐标建立两个树状数组即可。一个用来存储个数，一个用来存储坐标之和，那么对于第i头牛来说我们就能够在O(logn)的时间内求出countLeft和totalLeft

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>

#define MAXSIZE 20005

using namespace std;   //使用名称空间std

struct cow
{
	long long vi, xi;     //听力值和位置
};

long long val_sum_x[MAXSIZE];     //更新坐标值             
long long val_x[MAXSIZE];         //更新位置
cow arry[MAXSIZE];

int main()
{
	bool cmp(cow a, cow b);
	int lowbit(int x);
	void update_1(long long val[], long long i, long long cal, int arry_num);
	long long sum_pre_1(long long val[], int i);
	long long sum_between_1(long long val[], int pre, int last);

	int N;
	int left_x, right_x;
	long long left_sum, right_sum;
	long long sum_v;
	while (~scanf("%d", &N))
	{
		memset(val_x, 0, sizeof(val_x));
		memset(val_sum_x, 0, sizeof(val_sum_x));
		memset(arry, 0, sizeof(long long) * 2 * MAXSIZE);
		sum_v = 0;
		for (int i = 1;i <= N;i++)
			scanf("%lld%lld", &arry[i].vi, &arry[i].xi);
		sort(arry + 1, arry + 1 + N, cmp);
		for (int i = 1;i <= N;i++)
		{
			update_1(val_x, arry[i].xi, 1, MAXSIZE);
			update_1(val_sum_x, arry[i].xi, arry[i].xi, MAXSIZE);
			left_x = sum_between_1(val_x, 1, arry[i].xi - 1);
			right_x = sum_between_1(val_x, arry[i].xi + 1, MAXSIZE);
			left_sum = sum_between_1(val_sum_x, 1, arry[i].xi - 1);
			right_sum = sum_between_1(val_sum_x, arry[i].xi + 1, MAXSIZE);
			sum_v = sum_v + arry[i].vi*(left_x*arry[i].xi - left_sum) + arry[i].vi*(right_sum - right_x * arry[i].xi);
		}
		printf("%lld\n", sum_v);
	}
	return 0;
}

bool cmp(cow a, cow b)
{
	return a.vi < b.vi;
}

int lowbit(int x)
{//返回二进制数最低位的1对应的数值
	return x & (-x);      //与运算
}

//一维树状数组
void update_1(long long val[], long long i, long long cal, int arry_num)
{//原数组第i个元素加上cal，更新树状数组相关元素,arry_num为原数组的长度
 //可直接用于树状数组的建立
	for (;i <= arry_num;i += lowbit(i))
		val[i] += cal;
}

long long sum_pre_1(long long val[], int i)
{//求arry数组的前i项和
 //val为树状数组地址
	long long sum = 0;
	for (;i > 0;i -= lowbit(i))       //从后向前每次跳一个lowbit
		sum += val[i];
	return sum;
}

long long sum_between_1(long long val[], int pre, int last)
{//求原数组arry在区间[pre-last]的和
	return sum_pre_1(val, last) - sum_pre_1(val, pre - 1);
}

树状数组相关应用之二元问题

一维数组处理二元问题

相关推荐