UVA - 11983 Weird Advertisement （線段樹求並面積）

Description

G

Weird Advertisement

Renat Mullakhanov (rem), one of the most talented programmers in the world, passed away on March 11, 2011. This is very sad news for all of us. His team went to ACM ICPC World Finals - 2004, placed 4th and won gold medals. He really was a great programmer. May he rest in peace. This problem is dedicated to him.

2DPlaneLand is a land just like a huge 2D plane. The range of X axis is 0 to 10⁹ and the range of Y axis is also 0 to 10⁹. People built houses only in integer co-ordinates and there is exactly one house in each integer co-ordinate.

Now UseAndSmile Soap Company is launching a new soap. That's why they want to advertise this product as much as possible. So, they selected n persons for this task. Each person will be given a rectangular region. He will advertise the product to all the houses that lie in his region. Each rectangular region is identified by 4 integers x₁, y₁, x₂ and y₂. That means this person will advertise in all the houses whose x co-ordinate is between x₁ and x₂ (inclusive) and y co-ordinate is between y₁ and y₂ (inclusive).

Now after a while they realized that some houses are being advertised by more than one person. So, they want to find the number of houses that are advertised by at least k persons. Since you are one of the best programmers in the city; they asked you to solve this problem.

Input

Input starts with an integer T (≤ 13), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 30000), k (1 ≤ k ≤ 10). Each of the next n lines will contain 4 integers x₁, y₁, x₂, y₂ (0 ≤ x₁, y₁, x₂, y₂ ≤ 10⁹, x₁ < x₂, y₁ < y₂) denoting a rectangular region for a person.

Output

For each case, print the case number and the total number of houses that are advertised by at least k people.

Sample Input

Output for Sample Input

2

2 1

0 0 4 4

1 1 2 5

2 2

0 0 4 4

1 1 2 5

Case 1: 27

Case 2: 8

題意：給你n個矩形，求覆蓋大於等於k的點數

思路：將右上角的點x，y都加一就能轉換成求並面積了，還是上面的邊標記1，下面的邊標記-1，傳統的線段樹求並面積，容易錯的地方是在更新的時候，引用胡浩大大的一句話：這裡線段樹的一個結點並非是線段的一個端點,而是該端點和下一個端點間的線段,所以題目中r+1,r-1的地方可以自己好好的琢磨一下

#include 
#include 
#include 
#include 
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define ll long long
using namespace std;
const int maxn = 60005;
const int M = 160010;

int k;
struct Seg {
	int l, r, h, s;
	Seg() {}
	Seg(int a, int b, int c, int d) {
		l = a, r = b, h = c, s = d;
	}
	bool operator <(const Seg &tmp) const {
		if (h == tmp.h)
			return s > tmp.s;
		return h < tmp.h;
	}
} p[maxn<<2];
int sum[11][M<<2];
int cover[M<<2];
int w[M<<2];;

void pushup(int pos, int l, int r) {
	for (int i = 0; i <= k; i++)	
		sum[i][pos] = 0;
	if (cover[pos] >= k) {
		sum[k][pos] = w[r+1] - w[l];
		return;
	}
	if (r == l) {
		sum[cover[pos]][pos] = w[r+1] - w[l];
		return;
	}
	int tmp = 0;
	for (int i = 0; i <= k; i++) {
		if (i + cover[pos] < k)
			sum[i+cover[pos]][pos] = sum[i][lson(pos)] + sum[i][rson(pos)];
		else sum[k][pos] += sum[i][lson(pos)] + sum[i][rson(pos)];
	}
	for (int i = 1; i <= k; i++)
		tmp += sum[i][pos];
	sum[0][pos] = w[r+1] - w[l] - tmp;
}

void update(int L, int R, int l, int r, int pos, int op) {
	if (L <= l && R >= r) {
		cover[pos] += op;
		pushup(pos, l, r);
		return;
	}
	int m = l + r >> 1;
	if (L <= m)
		update(L, R, l, m, lson(pos), op);
	if (R > m)
		update(L, R, m+1, r, rson(pos), op);
	pushup(pos, l, r);
}

int search(int x, int r) {
	int l = 0;
	while (l <= r) {
		int m = l + r >> 1;
		if (w[m] == x)
			return m;
		else if (w[m] < x)
			l  = m + 1;
		else r = m - 1;
	}
	return -1;
}

void build(int l, int r, int pos) {
	sum[0][pos] = w[r+1] - w[l];
	if (l == r)
		return;
	int m = l + r >> 1;
	build(l, m, lson(pos));
	build(m+1, r, rson(pos));
}

int main() {
	int t, n, m, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &k);
		memset(cover, 0, sizeof(cover));
		memset(sum, 0, sizeof(sum));
		int tot = 0;
		int a, b, c, d;
		for (int i = 0; i < n; i++) {
			scanf("%d%d%d%d", &a, &b, &c, &d);
			c++, d++;
			p[tot] = Seg(a, c, b, 1);
			w[tot++] = a;
			p[tot] = Seg(a, c, d, -1);
			w[tot++] = c;
		}
		if (k > n) {
			printf("Case %d: 0\n", cas++);
			continue;
		}
		sort(w, w+tot);
		sort(p, p+tot);
		int cnt = unique(w, w+tot) - w;
		build(0, cnt-1, 1);
		ll ans = 0;
		for (int i = 0; i < tot-1; i++) {
			int l = search(p[i].l, cnt-1);
			int r = search(p[i].r, cnt-1)-1;
			update(l, r, 0, cnt-1, 1, p[i].s);
			ans += (ll)(sum[k][1] * (ll)(p[i+1].h - p[i].h));
		}
		printf("Case %d: ", cas++);
		printf("%lld\n", ans);
	}
	return 0;
}