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;}