directory

  • Tree array
  • sample
    • The question
    • Analysis of the
    • code
  • summary
  • Related to recommend

Tree array

  • What is a tree array? In simple terms, it is a violent traversal of a number to solve the interval problem, etc., but the traversal of the path is compressed with bit operation, complexity O(log2(n)) so that it does not time out. .
  • Lowbit () operation

    At its core is the magical Lowbit operation, lowbit(x)=x&(-x)The last 1 in the binary number of x, the principle is represented by the complement of negative numbers, which is the inverse plus one of the original code. For example, x = 6 = 00000110 (2), – x = x = 11111010 (2), then lowbit (x) = x & (x) = 10 (2) = 2.

    Lowbit () : a[x] : a[x] : a[x] : a[x] : a[x]



    Graphical:



    Then through a [] arrays, and can sum, such as sum (8) = [8], a sum (7) = a + a + [6] [7] a [4], the sum (6) = a [6] + [4], so not is the path of the compression?

    Similarly, to update ax, update a[]; for example, to update A3, change a[3] first; Then 3+lowbit(3)=4, change a[4]; Then 4+lowbit(4)=8, change a[8].

sample

Portal: HDU-3015

One day Sophia finds a very big square. There are n trees in the square. They are all so tall. Sophia is very interesting in them.



She finds that trees maybe disharmony and the Disharmony Value between two trees is associated with two value called FAR and SHORT.

The FAR is defined as the following:If we rank all these trees according to their X Coordinates in ascending order.The tree with smallest X Coordinate is ranked 1th.The trees with the same X Coordinates are ranked the same. For example,if There are 5 trees with X Coordinates 3,3,1,3,4. Then their ranks may be 2,2,1,2,5. The FAR of two trees with X Coordinate ranks D1 and D2 is defined as F = abs(D1-D2).

The SHORT is defined similar to The FAR. If we rank all these trees according to their heights in ascending order, the tree with shortest height is ranked 1th.The trees with the same heights are ranked the same. For example, If there are 5 trees with heights 4,1,9,7,4. Then their ranks may be 2,1,5,4 H1 and H2 is defined as S=min(H1,H2).

Two tree’s Disharmony Value is defined as F*S. So from the definition above we can see that, If two trees’ FAR is larger, the Disharmony Value is bigger. And the Disharmony value is also associated with the shorter one of the two trees.

Now give you every tree’s X Coordinate and their height, Please tell Sophia the sum of every two trees’ Disharmony value among all trees.

input:

There are several test cases in the input For each test case, The first line contains one integer N (2 <= N <= 100,000) N represents the number of trees. Then following N lines, each line contain two integers : X,H (0 < X,H <=1,000,000,000), indicating that the tree is located in Coordinates X and its height is H.

output:

For each test case output the sum of every two trees’ Disharmony value among all trees. The answer is within signed 64-bit integer.

Sample Input:

2
10 100
20 200
4
10 100
50 500
20 200
20 100
Copy the code

Sample Output:

1
13
Copy the code

The question

The coordinates X and height H of N trees are given, and the disharmony values of the two trees are defined as FAR*SHORT, where FAR= ABS (X1-X2), SHORT=min(h1,h2). Note that X and H at this time are the sorted ranking and have the same name. Find the total incongruity value.

Analysis of the

  1. Data processing: read pair< coordinate X, original subscript > X [], process the same name after sorting, the same height H, and finally get pair< relative coordinate, relative height > P [].
  2. Maintain two tree arrays: since SHORT=min(h1,h2), we sort p[] in descending order by height and iterate over p[] to get the current minimum height SHORT each time, then multiply by the FAR of all previous trees. So how do we find FAR? At this point, the maintenance array CNT [] represents the number, dis[] represents the coordinates, total FAR=FAR left +FAR right (because it is sorted by height, not coordinates, so there are left and right), FAR left = the number of trees on the left × the coordinates of the current tree – the sum of the coordinates of the left tree, so the distance between all trees on the left and the current tree can be obtained. Similarly, FAR right = the coordinates of the right tree and – the number of right trees × the coordinates of the current tree. At this point it’s good to maintain the array and update the answer.

code

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
pair<ll, ll>p[maxn], x[maxn], h[maxn];
int n;
ll cnt[maxn], dis[maxn];
bool cmp(pair<ll, ll>a, pair<ll, ll>b) {
	return a.second > b.second;
}
int lowbit(int x) {
	return x & (-x);
}
ll sum(ll* bit, int x) {
	ll res = 0;
	for (int i = x; i > 0; i -= lowbit(i))
		res += bit[i];
	return res;
}
ll sum(ll* bit, int from, int to) {
	return sum(bit, to - 1) - sum(bit, from - 1);
}
void update(ll* bit, int x, ll y) {
	for (int i = x; i <= maxn; i += lowbit(i))
		bit[i] += y;
}
int main(a) {
	while (~scanf("%d", &n)) {
		//1
		for (int i = 1; i <= n; i++) {
			scanf("%lld%lld", &x[i].first, &h[i].first);
			x[i].second = h[i].second = i;
		}
		sort(x + 1, x + n + 1);
		sort(h + 1, h + n + 1);
		ll tx = x[1].first, th = h[1].first, ans = 0;
		x[1].first = h[1].first = 1;
		for (int i = 2; i <= n; i++) {// handle the same name
			if (x[i].first == tx)
				x[i].first = x[i - 1].first;
			else {
				tx = x[i].first;
				x[i].first = i;
			}
			if (h[i].first == th)
				h[i].first = h[i - 1].first;
			else{ th = h[i].first; h[i].first = i; }}for (int i = 1; i <= n; i++) {
			p[x[i].second].first = x[i].first;
			p[h[i].second].second = h[i].first;
		}
		//2. Maintain two tree arrays
		sort(p + 1, p + 1 + n, cmp);// Height descending order
		memset(cnt, 0.sizeof(cnt));
		memset(dis, 0.sizeof(dis));
		for (int i = 1; i <= n; i++) {
			ll cx = p[i].first, ch = p[i].second;// The current tree coordinates and height
			ll left = sum(cnt, 1, cx), right = sum(cnt, cx + 1, maxn);// The number of left trees and the number of right trees
			ans += ch * (left * cx - sum(dis, 1, cx) + sum(dis, cx + 1, maxn) - right * cx);
			update(cnt, cx, 1);// Update the number
			update(dis, cx, cx);// Update the coordinates
		}
		printf("%lld\n", ans);
	}
	return 0;
}
Copy the code

summary

See sum, coordinates and other keywords, ordinary simulation will time out, you can consider converting into a tree array question to solve, the focus is how to convert, if you want to use multiple tree arrays, there will generally be maximum comparison sort.

Related to recommend

Recommend:

Post to recommend

  • Two-dimensional tree array -POJ 2155 Matrix
  • Differential marker -HDU1556 Color the ball

Original is not easy, please do not reprint (this is not rich visits add insult to injury) blogger home page: blog.csdn.net/qq_45034708 If the article is helpful to you, remember to focus on the likes collection ❤