ZOJ 3511 不相交切切多边形 线段树求最大边数
题意：
n多凸边形 m刀 （把n切m刀，问切完后的图形中 最多的边数 是多少）
切a点-b点
数据保证切的刀不会相交
思路：
2点之间的剩余点数就是边数，
把a-b距离 近 排序
切完一刀就统计一下切出来的蛋糕的边数，并舍弃
[a,b] 表示a,b 点间剩下的点数(就是边数)
先计算[a,b]的点数, 然后删除(a,b) 区间的点 (注意删除的是(a,b) ,所以实际操作是 删除[a,b] )
最后要特殊算下 剩下那块的(因为那块没有切)
#include<iostream>#include<stdio.h>#include<string>#include<string.h>#include<algorithm>#include<set>#include <cstdio> #include <cstring> #include <iostream> #include <math.h> #include <queue> #define N 10100 #define M 2000100 #define inf64 0x7ffffff #define inf 1073741824 #define ll int #define L(x) x<<1 #define R(x) x<<1|1 #define Mid(x,y) (x+y)>>1 using namespace std; inline ll Min(ll a,ll b){return a>b?b:a;} inline ll Max(ll a,ll b){return a>b?a:b;} struct Point{int x,y,dis;}p[N];bool cmp(Point a,Point b){return a.dis<b.dis;}struct node{ int l,r; ll sum;}tree[N*4]; void pushup(int id){tree[id].sum = tree[R(id)].sum + tree[L(id)].sum;}void build(int l,int r,int id){tree[id].l = l, tree[id].r = r;tree[id].sum = r - l + 1;if(l == r)return ;int mid = Mid(l,r);build( l, mid, L(id));build( mid+1, r, R(id));}void updata(int l, int r,int id){if(l == tree[id].l && tree[id].r == r){ tree[id].sum = 0; return ;}int mid=Mid(tree[id].l, tree[id].r);if(r <= mid)updata(l, r, L(id));else if(mid < l) updata(l, r, R(id));else {updata(l, mid, L(id));updata(mid+1, r, R(id));}pushup(id);}int query(int l, int r, int id){if(tree[id].sum==0)return 0;if( tree[id].l == tree[id].r)return tree[id].sum;int mid=Mid(tree[id].l, tree[id].r);if(r <= mid)return query(l, r, L(id));if(mid < l )return query(l, r, R(id));return query(l, mid, L(id)) + query(mid+1, r, R(id));}int main(){int n, m, i,temp;while(~scanf("%d %d",&n,&m)){for(i=1;i<=m;i++){scanf("%d %d",&p[i].x,&p[i].y);if(p[i].x>p[i].y)temp=p[i].x, p[i].x=p[i].y, p[i].y=temp;p[i].dis=p[i].y-p[i].x;}sort(p+1, p+m+1, cmp);build(1,n,1);int ans=0;for(i=1;i<=m;i++){ans=Max(ans, query(p[i].x, p[i].y, 1));updata(p[i].x+1, p[i].y-1, 1);}ans=Max(ans, query(1,n,1));printf("%d\n",ans);}return 0;}/*6 31 51 41 3ans:3*/