5.10校赛

May 15th, 2009 2 comments

很囧很囧。。。结果就不说了，Just 总结下目前会的题目。。
比赛地址
A：Accept
枚举4个点，判断是垂直，一个O(n^4)就能过
B：Choose ACMer
模拟题，注意09级比08级年轻，应该排在前面，，还有在计算最优的前n-2个分数时，，要直接用加的，不要用总的n个的和减去最差的2个，这样会造成精度问题。。
C：Heroes General Assembly
数论题。
题目即求a^b = 1 (mod c)中,b的最小值。
设b的最小值为e, 根据欧拉定理有，e | phi(c),其中phi(c)为欧拉函数，但是反过来并不成立，即不是充要条件。
所以我们先求出c的欧拉函数，然后对其分解素因子，再暴力枚举所有c的因子（不一定为素因子），取符合a^b = 1 (mod c)的最小值即可。
D：Largest Group
线段树。还没想到建树的方法。。
E：Magic String
找规律题。题目还没看。。
F：Put Coin Game
博弈题。试放所有位置的圆，求出每个table的SG值，再将所有的table的SG值求异或即可
G：Rotate rotate and rotate
几何题？？直接一个体积公式解决。注意PI要取acos(-1.0)….
H：Try
图论题。据说正解是拆点套用网络流，此方法不会-_-。偶是将每个钥匙能用几次就拆成几个点，然后建图套用二分图的最大匹配，，，如果数据过大，这方法就不行了。。。
I：Number Cutting Game
DP题。定义dp[i][j]=true代表前i个数，进行任意组合能得到余数j。那么有
if(dp[j][k]) dp[i][(k+num[j+1][i])%m] = true;{j<=i-1}
其实m为要模的数，num[j+1][i]代表数串中第j+1到第i个形成的数字对m求余的值。这个要首先通过预处理求得，否则会超时。总的复杂度为O(n^3)。
J：Number Reversing Game
搜索题。双向广搜+hash，赤裸裸的暴力。。
K：Special max_heap
组合数学？题目还没看。。。

Categories: ACM Tags: , ,

PKU City Horizon 3277

May 6th, 2009 No comments

题目地址
就是单纯的矩形面积交，速度相当的慢，唉。。实力不够。。。

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define MAXN 80001
struct {
    int c, l, r, lf, rf;
    ll cnt;
}nod[MAXN*3];
struct Line {
    int f, x, y1, y2;
}line[MAXN];
bool cmp(Line a, Line b) {
    return a.x < b.x;
}
int y[MAXN];
void creat(int t, int l, int r) {
    nod[t].c = nod[t].cnt = 0;
    nod[t].l = l, nod[t].r = r;
    nod[t].lf = y[l], nod[t].rf = y[r];
    if(l + 1 == r) return;
    int m = (l+r) / 2;
    creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
    if(nod[t].c > 0) {
        nod[t].cnt = nod[t].rf - nod[t].lf;
        return;
    }
    if(nod[t].l + 1 == nod[t].r) nod[t].cnt = 0;
    else nod[t].cnt = nod[t*2].cnt + nod[t*2+1].cnt;
}
void update(int t, Line e) {
    if(e.y1 == nod[t].lf && e.y2 == nod[t].rf) {
        nod[t].c += e.f;
        calen(t);
        return;
    }
    if(e.y2 <= nod[t*2].rf) update(t*2, e);
    else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
    else {
        Line tmp = e;
        tmp.y2 = nod[t*2].rf;
        update(t*2, tmp);
        tmp = e;
        tmp.y1 = nod[t*2+1].lf;
        update(t*2+1, tmp);
    }
    calen(t);
}
int main() {
    int n, i, t;
    int x1, x2, h, l;
	ll ans;
    while(scanf("%d", &n) != EOF) {
        t = 1;
        ans = 0;
		y[1] = 0;
        for(i = 1; i <= n; i++) {
            scanf("%d%d%d", &x1, &x2, &h);
            line[t].x = x1, line[t+1].x = x2;
            line[t].y1 = line[t+1].y1 = 0, line[t].y2 = line[t+1].y2 = h;
            line[t].f = 1, line[t+1].f = -1;
			y[i+1] = h;
            t += 2;
        }
        sort(line+1, line+t, cmp), sort(y+1, y+n+2);
		for(i = 2, l = 2; i < n + 2; i++) if(y[i] != y[i-1]) y[l++] = y[i];
        creat(1, 1, l-1);
        update(1, line[1]);
        for(i = 2; i < t; i++) {
            ans += nod[1].cnt * (line[i].x - line[i-1].x);
            update(1, line[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
Categories: ACM Tags: ,

HDU Picture 1828

May 6th, 2009 No comments

题目地址

给定一些矩形，求这些矩形围成的周长。（具体看题目的图）
很囧很囧，弄了我好多时间，，跟求矩形并的方法类似，但是加了判断结点覆盖的情况。
一开始，没有去掉y里重复的数值，而我在update时

 
if(nod[t].lf == e.y1 && nod[t].rf == e.y2) nod[t].cnt += e.f;
else {
	if(e.y2 <= nod[t*2].rf) update(t*2, e);
	else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
	else {
		Line tmp = e;
		tmp.y2 = nod[t*2].rf, update(t*2, tmp);
		tmp = e, tmp.y1 = nod[t*2+1].lf, update(t*2+1, tmp);
	}
}

 这种方法对于区间两端如果数值一样的话，是无法update到那个区间的，一个比较通用的方法是

 if(e.y1 <= nod[t].lf && nod[t].rf <= e.y2) nod[t].cnt += e.f;
else if(nod[t].l + 1 != nod[t].r) {
	int m = (nod[t].l+nod[t].r) / 2;
	if(e.y1 < y[m]) update(t*2, e);
	if(y[m] < e.y2) update(t*2+1, e);
}

 这样即使数值一样，也可以。突然想到，貌似之前几道矩形并交的题都是使用上面的那种方法，貌似都没有出问题，其实是因为求矩形面积并时如果有端点一样的情况，访问到那里其数值也是为0,因为长度为0,而对于这题，由于需要判断端点是否重复覆盖，故一定要访问到，在端点有一样的情况下，第一种方法就不适用了。
不过最后我还是通过把y去重，这样结点数会变少许多,orz…
Meomry: 492K
Time: 15MS

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int maxn = 10001;
struct {
	int l, r, lf, rf, ld, rd, cnt, len, lines;
}nod[maxn*3];
struct Line {
	int x, y1, y2, f;
	bool operator < (const Line &a) const {
		return x < a.x || x == a.x && f > a.f;
	}
}line[maxn];
int y[maxn];
void creat(int t, int l, int r) {
	nod[t].cnt = nod[t].len = nod[t].ld = nod[t].rd = nod[t].lines = 0;
	nod[t].l = l, nod[t].r = r, nod[t].lf = y[l], nod[t].rf = y[r];
	if(l + 1 == r) return;
	int m = (l+r) >> 1;
	creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
	nod[t].len = 0;
	if(nod[t].cnt > 0) nod[t].len = nod[t].rf - nod[t].lf;
	else if(nod[t].l + 1 != nod[t].r) nod[t].len = nod[t*2].len + nod[t*2+1].len;
}
void caline(int t) {
	nod[t].ld = nod[t].rd = nod[t].lines = 0;
	if(nod[t].cnt > 0) nod[t].ld = nod[t].rd = nod[t].lines = 1;
	else if(nod[t].l + 1 != nod[t].r) nod[t].ld = nod[t*2].ld, nod[t].rd = nod[t*2+1].rd, nod[t].lines = nod[t*2].lines + nod[t*2+1].lines - (nod[t*2].rd & nod[t*2+1].ld);
}
void update(int t, Line e) {
	if(nod[t].lf == e.y1 && nod[t].rf == e.y2) nod[t].cnt += e.f;
	else {
		if(e.y2 <= nod[t*2].rf) update(t*2, e);
		else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
		else {
			Line tmp = e;
			tmp.y2 = nod[t*2].rf, update(t*2, tmp);
			tmp = e, tmp.y1 = nod[t*2+1].lf, update(t*2+1, tmp);
		}
	}
	//if(e.y1 <= nod[t].lf && nod[t].rf <= e.y2) nod[t].cnt += e.f;
	//else if(nod[t].l + 1 != nod[t].r) {
	//	int m = (nod[t].l+nod[t].r) / 2;
	//	if(e.y1 < y[m]) update(t*2, e);
	//	if(y[m] < e.y2) update(t*2+1, e);
	//}
	calen(t), caline(t);
}
int main() {
	int n, x1, y1, x2, y2, i, t, s, preline, prelen, l;
	while(scanf("%d", &n) != EOF) {
		for(i = 0, t = 1; i < n; i++) {
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			line[t].x = x1, line[t+1].x = x2;
			line[t].y1 = line[t+1].y1 = y[t] = y1;
			line[t].y2 = line[t+1].y2 = y[t+1] = y2;
			line[t].f = 1, line[t+1].f = -1;
			t += 2;
		}
		sort(line+1, line+t), sort(y+1, y+t);
		for(i = 2, l = 2; i < t; i++) if(y[i] != y[i-1]) y[l++] = y[i];
		creat(1, 1, l-1);
		s = preline = prelen = 0;
		for(i = 1; i < t; i++) {
			update(1, line[i]);
			s += abs(nod[1].len-prelen) + 2 * preline * (line[i].x - line[i-1].x);
          	prelen = nod[1].len, preline = nod[1].lines;
		}
		printf("%d\n", s);
	}
	return 0;
}
Categories: ACM Tags: ,

FZU Huge Mission 1608

May 6th, 2009 No comments

题目地址
题目大致是说，oaiei大大在不同的时间段有不同的状态值，给定一个时间段，问这个时间段内oaiei大大可能的最大状态值是多少。让我不懂的是为啥一天的时间段能达到上万囧~0~
线段树构造的很挫，k记录该区间的最大状态值，f记录该区间下面的子区间的最大状态值。每次更新时，如果区间刚好等于结点区间，则判断是否大于k，如果满足，则直接覆盖k，如果大于f，也覆盖f,否则直接返回。如果不等于该区间，则根据情况递归更新左右子区间。查询时，只要结点的k>=f或者为叶子结点,则可以直接返回(r-l)*k的值，否则判断左右子结点k的值，只要小于父结点的k，就赋上父结点k的值。然后判断父结点的k是否大于子结点的f,小于哪一边，就递归到哪一边，另一边则直接返回对应区间长度*父结点的k。
一开始以为这样会比较好，不用更新到叶子结点，后来发现，如果题目数据比较特殊，即子结点区间的k值全大于父结点k值的话，则这样子写速度会更慢，-_-询求更好的方法。。。
Memory: 2370K
Time: 1.2S

#include <iostream>
using namespace std;
const int maxn = 50001;
struct {
	int l, r, k, f;
}nod[maxn*3];
void creat(int t, int l, int r) {
	nod[t].l = l, nod[t].r = r, nod[t].k = nod[t].f = 0;
	if(l + 1 == r) return;
	int m = (l+r) >> 1;
	creat(t*2, l, m), creat(t*2+1, m, r);
}
void update(int t, int l, int r, int k) {
	if(nod[t].k >= k) return;
	if(l == nod[t].l && nod[t].r == r) {
		nod[t].k = k;
		if(nod[t].f < k) nod[t].f = k;
		return;
	}
	if(nod[t].f < k) nod[t].f = k;
	if(r <= nod[t*2].r) update(t*2, l, r, k);
	else if(l >= nod[t*2+1].l) update(t*2+1, l, r, k);
	else update(t*2, l, nod[t*2].r, k), update(t*2+1, nod[t*2+1].l, r, k);
}
int query(int t, int l, int r) {
	if(nod[t].k >= nod[t].f || nod[t].l + 1 == nod[t].r) return (nod[t].r-nod[t].l) * nod[t].k;
	int ans = 0;
	if(nod[t].k > nod[t*2].k) nod[t*2].k = nod[t].k;
	if(nod[t].k > nod[t*2+1].k) nod[t*2+1].k = nod[t].k;
	if(nod[t].k < nod[t*2].f && nod[t].k >= nod[t*2+1].f) ans = query(t*2, l, nod[t*2].r) + (r-nod[t*2+1].l) * nod[t].k;
	else if(nod[t].k >= nod[t*2].f && nod[t].k < nod[t*2+1].f) ans = (nod[t*2].r-l) * nod[t].k + query(t*2+1, nod[t*2+1].l, r);
	else ans = query(t*2, l, nod[t*2].r) + query(t*2+1, nod[t*2+1].l, r);
	return ans;
}
int main() {
	int n, m, a, b, k;
	while(scanf("%d%d", &n, &m) != EOF) {
		creat(1, 0, n);
		while(m--) {
			scanf("%d%d%d", &a, &b, &k);
			update(1, a, b, k);
		}
		printf("%d\n", query(1, 0, n));
	}
	return 0;
}
Categories: ACM Tags: ,

PKU Count Color 2777

May 5th, 2009 No comments

题目地址
给指定区间的点染色，后染的颜色会覆盖掉前面染的。问经过一系列染色操作后，指定区间的点存在多少种颜色。
以前写过一次，那时对线段树的结点是这样定义的，如果col为-1,则代表该段区间为复合色，要继续递归找下去。这个有个缺点就是，如果要查询的区间刚好等于线段树某结点的区间，但是颜色为复合色，则当前无法知道具体有多少种颜色，必须递归查找到下面的子结点。明显这样就做了无用功了，我们要达到的目的是，查询的区间刚好等于线段树某结点的区间时可以直接返回。于是修改col代表的方式，因为颜色最多有30种，而2^31-1刚好能用int表示，所以我们用二进制来存储颜色信息。从最低位算起，第零位代表颜色1,第一位代表颜色2…因此，如果结点的每个区间的颜色有3,2,4这3种，那么col存的就是(1110)2=13,如果刚好要求区间等于该结点区间，则直接计算col二进制里1的个数，即为颜色的个数。而对于结点颜色的更新，父结点的col只要简单的求左右子结点col的或运算即可。
Memory: 3284K
Time: 250MS

#include <iostream>
using namespace std;const int maxn =100001;
#define SWAP(a,b) ((a)^=(b)^=(a)^=(b))
struct{int l,r,col;}nod[maxn*3];
bool test(int n){return (n &(n-1))==0;}
void creat(int t,int l,int r){nod[t].l =l,nod[t].r =r,nod[t].col =1;if(l ==r)return;int m =(l+r)>>1;creat(t*2,l,m),creat(t*2+1,m+1,r);}
void insert(int t,int l,int r,int c){if(c ==nod[t].col)return;if(l ==nod[t].l &&r ==nod[t].r){nod[t].col =c;return;}if(test(nod[t].col))nod[t*2].col =nod[t*2+1].col =nod[t].col;if(r <=nod[t*2].r)insert(t*2,l,r,c);else if(l >=nod[t*2+1].l)insert(t*2+1,l,r,c);else insert(t*2,l,nod[t*2].r,c),insert(t*2+1,nod[t*2+1].l,r,c);nod[t].col =nod[t*2].col |nod[t*2+1].col;}
void query(int t,int l,int r,int &cnt){if(l ==nod[t].l &&nod[t].r ==r ||test(nod[t].col)){cnt =cnt |nod[t].col;return;}if(r <=nod[t*2].r)query(t*2,l,r,cnt);else if(l >=nod[t*2+1].l)query(t*2+1,l,r,cnt);else query(t*2,l,nod[t*2].r,cnt),query(t*2+1,nod[t*2+1].l,r,cnt);}
int cal(int t,int l,int r){int cnt =0,c =0;query(t,l,r,cnt);while(cnt){if(cnt &1)c++;cnt >>=1;}return c;}
int main(){int l,t,o,a,b,c;char op[2];while(scanf("%d%d%d",&l,&t,&o)!=EOF){creat(1,1,l);while(o--){scanf("%s%d%d",op,&a,&b);if(a >b)SWAP(a,b);switch(op[0]){case'C':scanf("%d",&c);insert(1,a,b,1<<(c-1));break;default:printf("%d\n",cal(1,a,b));}}}return 0;}
Categories: ACM Tags: ,

PKU Tunnel Warfare 2892

May 3rd, 2009 1 comment

题目地址
题目大意是给出一系列的村庄，如果相邻村庄都没有被破坏，则两村庄是连接的，题目给出一系列的破坏操作，对指定号码的村庄进行破坏，还有一系列的询问操作，询问与指定号码的村庄直接相连或间接相连的村庄有几个，还有一个修复操作，是对最后破坏的村庄进行修复。
这题构造的线段树有点特殊，每个村庄的号码不是在叶子结点中存放，而是在每个结点中，左右中间的中间值做为村庄号码的编号id,比如一个结点的区间为1到10,那么该结点代表了村庄(1+10)>>1即5,另外左右子结点分别是[l,id-1],[id+1,r],这样定义的好处是对于某个编号id,其左边连续村庄数lf可由左子结点得出，右边连续村庄数rf可右右子结点得出。同时每个结点存一个标志位f,代表该结点所代表的村庄编号有没被毁坏。
当修复或者破坏操作执行时，如果破坏或修复的编号刚好等于结点的id,则直接将f置为相应的编号返回，如果不等于，如果要操作的编号<结点的id,那么势必在其左子结点进行操作，递归操作左子结点，而后对于rf是没有影响的，我们只要重新确定lf。如果要操作的编号小于左子结点的id,而且左子结点已经被毁坏或者或者其左子结点右边连续的村庄数没有到达该结点的右区间，则不用操作，否则对该结点执行getR()操作。
getR()的操作具体如下：
它是取得某个结点对应村庄左边连续村庄的数量，而对于此，我们必须对它的左子结点进行操作，如果左子结点对应村庄右边连续区域刚好等于右区间数，即父结点与左子结点对应的村庄是连接着的，那么就把左子结点的rf加上：一，如果左子结点对应村庄已毁，则加0。二，加上lf+1。如果父结点与左子结点对应的村庄不是连接的，则递归对左子结点的右子结点进行getR()操作。
对于getL()操作类似。

#include <iostream>
using namespace std;
#define MAXN 50001
struct {
	int l, r, lc, rc, f, id;
} nod[MAXN*3];
unsigned int st[MAXN], l;
void creat(int t, int l, int r) {
	nod[t].l = l, nod[t].r = r, nod[t].f = 1;
	nod[t].id = (l+r) >> 1;
	nod[t].lc = nod[t].id - l, nod[t].rc = r - nod[t].id;
	if(nod[t].id != l) creat(t*2, l, nod[t].id-1);
	if(nod[t].id != r) creat(t*2+1, nod[t].id+1, r);
}
int getL(int t) {
	if(nod[t].id - nod[t].l == nod[t].lc) return nod[t].lc + (nod[t].f ? nod[t].rc + nod[t].f : 0);
	return getL(t*2);
}
int getR(int t) {
	if(nod[t].r - nod[t].id == nod[t].rc) return nod[t].rc + (nod[t].f ? nod[t].lc + nod[t].f : 0);
	return getR(t*2+1);
}
void RandD(int t, int num, int f) {
	if(num == nod[t].id) nod[t].f = f;
	else if(num < nod[t].id) {
		RandD(t*2, num, f);
		if(!(num < nod[t*2].id && (!nod[t*2].f || nod[t*2].r - nod[t*2].id > nod[t*2].rc))) nod[t].lc = getR(t*2);
	} else {
		RandD(t*2+1, num, f);
		if(!(num > nod[t*2+1].id && (!nod[t*2+1].f || nod[t*2+1].id - nod[t*2+1].l > nod[t*2+1].lc))) nod[t].rc = getL(t*2+1);
	}
}
int query(int t, int num) {
	if(num == nod[t].id) return nod[t].f ? nod[t].f + nod[t].lc + nod[t].rc : 0;
	else if(num < nod[t].id) {
		if(num >= nod[t].id - nod[t].lc) return nod[t].lc + (nod[t].f ? nod[t].f + nod[t].rc : 0);
		else return query(t*2, num);
	} else {
		if(num <= nod[t].id + nod[t].rc) return nod[t].rc + (nod[t].f ? nod[t].f + nod[t].lc : 0);
		else return query(t*2+1, num);
	}
}
int main() {
	int n, m, t;
	char s[2];
	while(scanf("%d%d", &n, &m) != EOF) {
		l = 0;
		creat(1, 1, n);
		while(m--) {
			scanf("%s", s);
			switch(s[0]) {
				case 'D':
					scanf("%d", &t);
					st[l++] = t;
					RandD(1, t, 0);
					break;
				case 'R':
					RandD(1, st[--l], 1);
					break;
				default:
					scanf("%d", &t);
					printf("%d\n", query(1, t));
			}
		}
	}
	return 0;
}
Categories: ACM Tags: ,

HDU 覆盖的面积 1255

April 30th, 2009 No comments

题目地址
题目要求覆盖大于等于二次以上的面积，其实就是求矩形面积的交集。
想法跟1542的差不多，加了个重复测度
Memory: 492K
Time: 343MS

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 2001
struct {
	int c, l, r;
	double cnt, recnt, lf, rf;
}nod[MAXN*3];
struct Line {
	double x, y1, y2;
	int f;
}line[MAXN];
bool cmp(Line a, Line b) {
	return a.x < b.x;
}
double y[MAXN];
void creat(int t, int l, int r) {
	nod[t].c = nod[t].cnt = nod[t].recnt = 0;
	nod[t].l = l, nod[t].r = r;
	nod[t].lf = y[l], nod[t].rf = y[r];
	if(l + 1 == r) return;
	int m = (l+r) / 2;
	creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
	if(nod[t].c > 0) {
		nod[t].cnt = nod[t].rf - nod[t].lf;
		return;
	}
	if(nod[t].l + 1 == nod[t].r) nod[t].cnt = 0;
	else nod[t].cnt = nod[t*2].cnt + nod[t*2+1].cnt;
}
void carelen(int t) {
	if(nod[t].c > 1) {
		nod[t].recnt = nod[t].rf - nod[t].lf;
		return;
	}
	if(nod[t].l + 1 == nod[t].r) nod[t].recnt = 0;
	else {
		if(nod[t].c == 1) nod[t].recnt = nod[t*2].cnt + nod[t*2+1].cnt;
		else nod[t].recnt = nod[t*2].recnt + nod[t*2+1].recnt;
	}
}
void update(int t, Line e) {
	if(e.y1 == nod[t].lf && e.y2 == nod[t].rf) {
		nod[t].c += e.f;
		calen(t);
		carelen(t);
		return;
	}
	if(e.y2 <= nod[t*2].rf) update(t*2, e);
	else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
	else {
		Line tmp = e;
		tmp.y2 = nod[t*2].rf;
		update(t*2, tmp);
		tmp = e;
		tmp.y1 = nod[t*2+1].lf;
		update(t*2+1, tmp);
	}
	calen(t);
	carelen(t);
}
int main() {
	int n, i, t, cases;
	double x1, x2, y1, y2, ans;
	scanf("%d", &cases);
	while(cases--) {
		scanf("%d", &n);
		t = 1;
		ans = 0;
		for(i = 1; i <= n; i++) {
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			line[t].x = x1, line[t+1].x = x2;
			line[t].y1 = line[t+1].y1 = y[t] = y1, line[t].y2 = line[t+1].y2 = y[t+1] = y2;
			line[t].f = 1, line[t+1].f = -1;
			t += 2;
		}
		sort(line+1, line+t, cmp), sort(y+1, y+t);
		creat(1, 1, t-1);
		update(1, line[1]);
		for(i = 2; i < t; i++) {
			ans += nod[1].recnt * (line[i].x - line[i-1].x);
			update(1, line[i]);
		}
		printf("%.2lf\n", ans);
	}
	return 0;
}
Categories: ACM Tags: ,

HDU Atlantis 1542

April 30th, 2009 No comments

题目地址
题目意思很简单，要求计算被矩形覆盖过的面积，即求矩形面积的并集
对顶点进行离散化，对顶点的Y坐标从小到大排序，然后以这些点建立线段树。结点存储该区间被完全覆盖的次数c,该区间的测试cnt,以及对Y坐标的映射。对于每一个X坐标，如果是线段的起点，则覆盖次数加1,代表线段开始，如果是线段的终点，则减1,代表该线段覆盖的范围已经结束
Memory: 248K
Time: 0MS

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 201
struct {
	int c, l, r;
	double cnt, lf, rf;
}nod[MAXN*3];
struct Line {
	double x, y1, y2;
	int f;
}line[MAXN];
bool cmp(Line a, Line b) {
	return a.x < b.x;
}
double y[MAXN];
void creat(int t, int l, int r) {
	nod[t].c = nod[t].cnt = 0;
	nod[t].l = l, nod[t].r = r;
	nod[t].lf = y[l], nod[t].rf = y[r];
	if(l + 1 == r) return;
	int m = (l+r) / 2;
	creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
	if(nod[t].c > 0) {
		nod[t].cnt = nod[t].rf - nod[t].lf;
		return;
	}
	if(nod[t].l + 1 == nod[t].r) nod[t].cnt = 0;
	else nod[t].cnt = nod[t*2].cnt + nod[t*2+1].cnt;
}
void update(int t, Line e) {
	if(e.y1 == nod[t].lf && e.y2 == nod[t].rf) {
		nod[t].c += e.f;
		calen(t);
		return;
	}
	if(e.y2 <= nod[t*2].rf) update(t*2, e);
	else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
	else {
		Line tmp = e;
		tmp.y2 = nod[t*2].rf;
		update(t*2, tmp);
		tmp = e;
		tmp.y1 = nod[t*2+1].lf;
		update(t*2+1, tmp);
	}
	calen(t);
}
int main() {
	int n, i, t, cases = 1;
	double x1, x2, y1, y2, ans;
	while(scanf("%d", &n), n) {
		t = 1;
		ans = 0;
		for(i = 1; i <= n; i++) {
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			line[t].x = x1, line[t+1].x = x2;
			line[t].y1 = line[t+1].y1 = y[t] = y1, line[t].y2 = line[t+1].y2 = y[t+1] = y2;
			line[t].f = 1, line[t+1].f = -1;
			t += 2;
		}
		sort(line+1, line+t, cmp), sort(y+1, y+t);
		creat(1, 1, t-1);
		update(1, line[1]);
		for(i = 2; i < t; i++) {
			ans += nod[1].cnt * (line[i].x - line[i-1].x);
			update(1, line[i]);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", cases++, ans);
	}
	return 0;
}
Categories: ACM Tags: ,

HDU I Hate It 1754

April 27th, 2009 No comments

题目地址
询问区间最值，并执行某个点的变更操作
没什么好说的，线段树的入门基础题。
Memory: 7148K
Time: 468MS

#include <iostream>
using namespace std;
inline int Max(int a, int b){return a > b ? a : b;}
const int MAXN = 200001;
struct {
	int l, r, m;
} nod[MAXN*3];
int a[MAXN];
void creat(int t, int l, int r) {
	nod[t].l = l, nod[t].r = r;
	if(l == r) {nod[t].m = a[l]; return;}
	int m = (l+r) / 2;
	creat(t*2, l, m), creat(t*2+1, m+1, r);
	nod[t].m = Max(nod[t*2].m, nod[t*2+1].m);
}
int query(int t, int l, int r) {
	if(l == nod[t].l && r == nod[t].r) return nod[t].m;
	int s;
	if(r <= nod[t*2].r) s = query(t*2, l, r);
	else if(l >= nod[t*2+1].l) s= query(t*2+1, l, r);
	else s = Max(query(t*2, l, nod[t*2].r), query(t*2+1, nod[t*2+1].l, r));
	return s;
}
void update(int t, int n, int v) {
	if(nod[t].l == nod[t].r && nod[t].l == n) {nod[t].m = v; return;}
	if(n <= nod[t*2].r) update(t*2, n, v);
	else update(t*2+1, n, v);
	nod[t].m = Max(nod[t*2].m, nod[t*2+1].m);
}
int main() {
	int n, m, i, x1, x2;
	char s[2];
	while(scanf("%d%d", &n, &m) != EOF) {
		for(i = 1; i <= n; i++) scanf("%d", &a[i]);
		creat(1, 1, n);
		while(m--) {
			scanf("%s%d%d", s, &x1, &x2);
			if(s[0] == 'Q') printf("%d\n", query(1, x1, x2));
			else update(1, x1, x2);
		}
	}
	return 0;
}
Categories: ACM Tags: ,

HDU Just a Hook 1698

April 27th, 2009 No comments

题目地址
给一组棍子染色，不同的颜色有不同的值，执行一系列的区间染色后，问这组棍子的总值是多少。
每个线段树的结点，存储该结点所代表区间的染色状况c，如果该区间全为同样的颜色，则用一个正数表示，如果含有多种颜色，则用-1表示，每次执行染色操作时，如果所要染的颜色与区间颜色一样，则停止，如果所要染区间跟当前结点区间一致，则直接将所要染颜色赋给当前结点的c,否则，如果当前结点区间不是混合色，则先将当前结点的颜色赋给左右子结点的c,并递归下去。
Memory: 3284k
Time: 406MS

#include <iostream>
using namespace std;
const int MAXN = 100001;
struct {
	int l, r, c;
} nod[MAXN*3];
void creat(int t, int l, int r) {
	nod[t].l = l, nod[t].r = r, nod[t].c = 1;
	if(l == r) return;
	int m = (l+r) / 2;
	creat(t*2, l, m), creat(t*2+1, m+1, r);
}
void color(int t, int l, int r, int c) {
	if(c == nod[t].c) return;
	if(l == nod[t].l && r == nod[t].r) {nod[t].c = c; return;}
	if(nod[t].c != -1) nod[t*2].c = nod[t*2+1].c = nod[t].c;
	nod[t].c = -1;
	if(r <= nod[t*2].r) color(t*2, l, r, c);
	else if(l >= nod[t*2+1].l) color(t*2+1, l, r, c);
	else color(t*2, l, nod[t*2].r, c), color(t*2+1, nod[t*2+1].l, r, c);
}
int count(int t, int l, int r) {
	if(nod[t].c > 0) return (r-l+1) * nod[t].c;
	return count(t*2, l, nod[t*2].r) + count(t*2+1, nod[t*2+1].l, r);
}
int main() {
	int cases, n, q, x1, x2, c, t = 1;
	scanf("%d", &cases);
	while(cases--) {
		scanf("%d%d", &n, &q);
		creat(1, 1, n);
		while(q--) {scanf("%d%d%d", &x1, &x2, &c); color(1, x1, x2, c);}
		int aa;
		printf("Case %d: The total value of the hook is %d.\n", t++, count(1, 1, n));
	}
	return 0;
}
Categories: ACM Tags: ,