ZOJ 3511 Cake Robbery(線段樹)

ZOJ 3511 Cake Robbery

題目鏈接

題意：給定一個n邊形，切m刀，問切了之後最大邊數的子塊邊數是多少，保證切的邊不會交叉

思路：由於有保證切的邊不交叉這個條件，所以可以按切掉點數排序，點數最少優先切，因為點數最少肯定是被包含了，這樣一刀刀切過去，切過的點就剔除掉，並記錄下最大值，利用線段樹維護即可

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 10005;

int n, m;

struct Query {
	int l, r;
	void read() {
		scanf("%d%d", &l, &r);
		if (l > r) swap(l, r);
	}
} q[N];

bool cmp(Query a, Query b) {
	return a.r - a.l < b.r - b.l;
}

#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)

struct Node {
	int l, r, sum;
	int lazy;
	void gao() {
		lazy = 1;
		sum = 0;
	}
} node[N * 4];

void pushup(int x) {
	node[x].sum = node[lson(x)].sum + node[rson(x)].sum;
}

void pushdown(int x) {
	if (node[x].lazy) {
		node[lson(x)].gao();
		node[rson(x)].gao();
		node[x].lazy = 0;
	}
}

void build(int l, int r, int x = 0) {
	node[x].l = l; node[x].r = r; node[x].lazy = 0;
	if (l == r) {
		node[x].sum = 1;
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, lson(x));
	build(mid + 1, r, rson(x));
	pushup(x);
}

void add(int l, int r, int x = 0) {
	if (node[x].l >= l && node[x].r <= r) {
		node[x].gao();
		return;
	}
	int mid = (node[x].l + node[x].r) / 2;
	pushdown(x);
	if (l <= mid) add(l, r, lson(x));
	if (r > mid) add(l, r, rson(x));
	pushup(x);
}

int query(int l, int r, int x = 0) {
	if (node[x].l >= l && node[x].r <= r)
		return node[x].sum;
	int mid = (node[x].l + node[x].r) / 2;
	int ans = 0;
	pushdown(x);
	if (l <= mid) ans += query(l, r, lson(x));
	if (r > mid) ans += query(l, r, rson(x));
	pushup(x);
	return ans;
}

int main() {
	while (~scanf("%d%d", &n, &m)) {
		build(1, n);
		int l, r;
		for (int i = 0; i < m; i++)
			q[i].read();
		sort(q, q + m, cmp);
		int ans = 0;
		for (int i = 0; i < m; i++) {
			ans = max(ans, query(q[i].l, q[i].r));
			add(q[i].l + 1, q[i].r - 1);
		}
		ans = max(ans, node[0].sum);
		printf("%d\n", ans);
	}
	return 0;
}