POJ1990 -- MooFest (converted into a tree array)


If V is v1,v2, x is X1 and x2, then the value between them is ABS (x1-x2)* Max (v1, v2), and the sum of values between all n*(n-1)/2 pairs of cattle is calculated.

Train of thought:

After reading https://blog.csdn.net/bestsort/article/details/80853221, it's nice to have a picture. It's clear after a while. The following picture is also from there.
According to the meaning of the title, it is to ask:

The order of cattle according to the value of v can be changed to:

In this way, when dealing with the first bull, its v value is the largest at present, the rest to be considered is the distance difference of coordinates.
Assuming that the first cow is currently being processed, its V value must be the largest in 1 to i. Since it is sorted by v, all the cows with V value can be divided into two categories, one is that the coordinates are on its left and the other is on its right.
For the cattle on the left, only the sum L of their distance from the first cow is needed. L = ln * Xi - S;
(xi is the coordinate of the first cow, ln is the number of cows with coordinates < Xi on the left, and S is the sum of coordinates of these cows.)

For the cattle on the right, the sum of their distance from the first cow is R, R = totdis - S - rn*Xi; rn = i-1-ln.
Let the sum of the current cumulative coordinates be totdis. Using the sum of the coordinates on the left as S, rn is the number of cattle with all coordinates < Xi on the right.

Pay attention to long distance

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
using namespace std;
LL n, C[2][maxn];

struct Node{
	int v,x;
	bool operator < (const Node& rhs) const{
		return v < rhs.v;

inline int lowbit(int x){ return x & -x; }
void add(int x, int v, int u){for(int i = x; i < maxn; i+= lowbit(i)) C[u][i]+= v;}
LL sum(int x, int u){
	LL s = 0;
	for(int i = x; i > 0; i-= lowbit(i)) s+= C[u][i];
	return s;

int main()
    LL totdis,ans;
	while(scanf("%d",&n) == 1){
		memset(C, 0, sizeof(C));
		totdis = 0; ans = 0;
		for(int i = 1; i <= n; ++i) scanf("%d%d", &nodes[i].v, &nodes[i].x);
		sort(nodes+1, nodes+n+1);
		for(int i = 1; i <= n; ++i){
			LL ln = sum(nodes[i].x, 0);		// Number of coordinates < x on the left 
			LL lw = sum(nodes[i].x, 1); 	// The sum of coordinates < x on the left
			LL L = ln*nodes[i].x - lw;
			LL rn = i-1 - ln;					// Number of right coordinates < x 
			LL R = totdis - lw - rn*nodes[i].x;
			ans+= (L+R)*nodes[i].v;
			totdis+= nodes[i].x;			// Total coordinate length
			add(nodes[i].x, 1, 0);
			add(nodes[i].x, nodes[i].x, 1);
		printf("%lld\n", ans);
	return 0;

Tags: REST Linker

Posted on Fri, 11 Oct 2019 10:28:20 -0700 by JPark