线段树 – edward

给定若干个平行于坐标轴的矩形，每种矩形有RGB 3种颜色中的一种。
问最后R G B RG GB RB RGB的色块面积有多大。

按x y轴离散化，按x递增序扫描过去，用线段树维护区间内每个色块的面积，叠加即可。
关键在于线段树怎么维护这样一个问题:

每次对一个区间进行+1 或-1操作, 保证-1前面有一个+1与之一一对应, 每次询问整个区间里非零元素的个数.

有了上面黑色的条件, 就可以不用标记下传做到这件事情了.
线段树上的每个结点都记录这么几个东西就可以维护出答案了.

struct Node {
    int l, r, mask;
    int c[3];
    lld sum[8];
    Node *lc, *rc;
}pool[500000], *root;

其中mask表示c里不为0的元素的mask.
c[3]表示该线段被第i种颜色完整覆盖的次数.
sum[8]表示每个mask的长度…
操作的时候只需要根据c[3] fix一下mask的值, 再一路update回根就好了.

Hint
对于颜色只有一种的情况, 除了这种tag线段被完全覆盖的次数的方法外, 还可以记录区间被覆盖次数的最小值以及其对应的长度, 就可以作出矩形的面积并.
其实就相当于区间+-, 然后求整体最小值的这种典型的线段树.
这种思路可以用于区间随意+-, 然后求长度的题目(也就是说可以搞定去掉上面黑体的那个条件的情况).
但是这种思路的线段树似乎很难用到这种有多种颜色的情况上面去…
路过的大神求指导…

附代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }

int Tc;
int n;
struct Seg {
	int l, r, c;
	Seg(int l, int r, int c): l(l), r(r), c(c) {}
};
map  > Ins;
map  > Era;
map  refy;
vector  coorx;
vector  coory;

struct Node {
	int l, r, mask;
	int c[3];
	lld sum[8];
	Node *lc, *rc;
}pool[500000], *root;
int nodeCnt;

void update(Node *p) {
	memset(p->sum, 0, sizeof(p->sum));
	if (p->l != p->r) {
		for (int i = 0; i < 8; i++) {
			p->sum[i | p->mask] += p->lc->sum[i] + p->rc->sum[i];
		}
	} else {
		p->sum[p->mask] = coory[p->l + 1] - coory[p->l];
	}
}

void build(Node *&p, int l, int r) {
	p = &pool[nodeCnt++];
	p->l = l;
	p->r = r;
	p->mask = 0;
	p->lc = p->rc = NULL;
	memset(p->c, 0, sizeof(p->c));
	memset(p->sum, 0, sizeof(p->sum));
	int mid = (l + r) / 2;
	if (l < r) {
		build(p->lc, l, mid);
		build(p->rc, mid + 1, r);
	}
	update(p);
}

void add(Node *p, int l, int r, int c, int delta) {
	if (l <= p->l && p->r <= r) {
		p->c += delta;
		if (p->c == 0 || (p->c == 1 && delta > 0)) {
			p->mask ^= 1 << c;
		}
		update(p);
	} else {
		int mid = (p->l + p->r) / 2;
		if (l <= mid) {
			add(p->lc, l, r, c, delta);
		}
		if (r > mid) {
			add(p->rc, l, r, c, delta);
		}
		update(p);
	}
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	char buf[10];
	scanf("%d", &Tc);
	for (int ri = 1; ri <= Tc; ri++) {
		Ins.clear();
		Era.clear();
		refy.clear();
		coorx.clear();
		coory.clear();
		set  Setx;
		set  Sety;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			int a, b, c, d;
			scanf("%s%d%d%d%d", buf, &a, &b, &c, &d);
			int o = buf[0] == 'R' ? 0 : (buf[0] == 'G' ? 1 : 2 );
			Ins[a].push_back(Seg(b, d, o));
			Era[c].push_back(Seg(b, d, o));
			Setx.insert(a);
			Setx.insert(c);
			Sety.insert(b);
			Sety.insert(d);
		}
		foreach (it, Setx) coorx.push_back(*it);
		foreach (it, Sety) coory.push_back(*it);
		for (int i = 0; i < coory.size(); i++) refy[coory[i]] = i;
		nodeCnt = 0;
		build(root, 0, coory.size() - 2);
		lld ans[8];
		memset(ans, 0, sizeof(ans));
		for (int i = 0; i + 1 < coorx.size(); i++) {
			vector  &In = Ins[coorx[i]];
			vector  &Out = Era[coorx[i]];
			foreach (it, In) add(root, refy[it->l], refy[it->r] - 1, it->c, 1);
			foreach (it, Out) add(root, refy[it->l], refy[it->r] - 1, it->c, -1);
			for (int j = 0; j < 8; j++) ans[j] += root->sum[j] * (coorx[i + 1] - coorx[i]);
		}
		printf("Case %d:\n", ri);
		printf("%I64d\n", ans[1]);
		printf("%I64d\n", ans[2]);
		printf("%I64d\n", ans[4]);
		printf("%I64d\n", ans[3]);
		printf("%I64d\n", ans[5]);
		printf("%I64d\n", ans[6]);
		printf("%I64d\n", ans[7]);
	}
}

标签存档：线段树

HDOJ 4419 Colourful Rectangle