分类存档：默认分类

HDOJ 4419 Colourful Rectangle

给定若干个平行于坐标轴的矩形， 每种矩形有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]);
	}
}

似乎ipad上的wordpress自带刷评论功能-.-, 我就用它登陆了一下, 过了一会儿就有几条这样子的东西出现了… “Extremely helpful information specially the last part 🙂 I care for such info a lot. I was seeking this particular info for a long time. Thank you and best of luck.”

ACM-ICPC 2012 Hangzhou Online Contest

今天真心圡成狗…写写流水账.

今天一上来我直接看了第二题和第三题, 但是似乎不是特别好写. 这时候zYc学长发现了一道典型的数据结构题(1008).
告诉我题意以后马上就得出了线段树套线性表的做法, 但是刚敲完读入, 发现只要离线树状数组搞就可以了. 于是1Y.

然后zYc跳1006, prowindy跳1005.
本来1005是全场秒杀题, 但是不知道为什么prowindy的代码WA了, zYc学长似乎有各种题意上的理解偏差, 也一直卡着.
1002这时候已经有人过了, 我去看了一下就发现是费用流, 但是因为自己太圡了, 还搞了半小时才调对sample, 然后1Y.

这时board上来看, 1005已经成了万人轮的题目. 于是跑去扫了一遍prowindy的代码.
没看出有什么问题. 虽然直觉上觉得那个度数判定可能有点问题, 但是想了一下好像又是对的. 然后就让prowindy重写一遍去了… 然后重写了一遍改了点小错误就Y了.
接下来zYc学长在clarification上各种刷, prowindy去帮zYc搞1006. 于是我就去写1007的后缀数组, 一开始写的直接用sort的, 复杂度$$O(n \log^2 n)$$ TLE了.
各种尝试未果, T死在那里.
于是找个DC3 $$O(n)$$ 的模板, 怎么交怎么RE. 直接被弄出阴影来了… 上次训练也是用罗穗骞的, 结果传一个串, 什么都没干就RE了… 交了几次RE以后, 就用了小hh的倍增模板$$O(n \log n)$$. 一交直接Y了.
果然还是hh靠谱…(让你天天不整理模板, 现在出事了吧…)
关于模板这个问题, 其实被坑过很多遍, 主要是平常我自己刷题习惯不使用模板, 导致没什么模板积累. 但是这样比赛可是要吃大亏的!!!

然后在我圡爆的时候, 队友也把1006搞出来了.

于是看一下board, 剩下的分工就很明确了. 让zYc去搞1003, 我和prowindy一起想了一下1010, 未果(脑子抽了当时居然连线段树求矩形并面积都不会了)… 然后我看了一下1009, 发现似乎是很裸的求期望的题目, 先bfs求可行性, 然后gauss消出期望就好了. 搞过了sample, 一交就RTE… 然后比赛就结束了.

感觉比赛里我比较圡的有这么几点:

  1. Suffix Array 没做好模板, 别人的又不习惯. 导致1007卡了好久.
  2. 1010的那个矩形并都反应不出来怎么搞了… -.-, 习惯了平常直接传各种标记的方式. 实在是太圡了.
  3. 帮prowindy看万人轮的1005, 也没看出什么错误… challenge能力有待加强了.
  4. 平常没怎么用力刷题, 手速没7月集训快了5555, 状态略显糟糕.

BTW, prowindy同学似乎感冒了的样子, 离Regional不远了… 注意身体.