题意:有一个N凸边形,顺时针编号1到N,沿对角线切了M刀,保证任意两刀之间不相交(除了端点),问在切这M刀的过程中,得到的凸多边形的最大的边数是多少。第一行给出N和M后,接下来的M行里,每行给出这刀切的起点端点st和终点端点ed。
多边形的边数等于点数。感觉方法很巧妙,将每个操作,按切掉的点的个数从小到大排序(点的个数这里可以看作ed-st+1)。当切掉这部分的时候,就将线段树里的这个范围内的点全部去除(成段更新)。在这个过程中,找出最大解就可以了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define LL(x) (x<<1) #define RR(x) (x<<1|1) #define MID(a,b) (a+((b-a)>>1)) const int N=10005; struct OP { int st,ed; void get() { scanf("%d%d",&st,&ed); if(st>ed) swap(st,ed); } bool operator<(const OP &b)const { return ed-st+1<b.ed-b.st+1; } }op[N]; struct node { int lft,rht,cnt,flag; int mid(){return MID(lft,rht);} void init(){cnt=rht-lft+1;flag=0;} void fun(){flag=1;cnt=0;} }; struct Segtree { node tree[N*4]; void down(int ind) { if(tree[ind].flag) { tree[LL(ind)].fun(); tree[RR(ind)].fun(); tree[ind].flag=0; } } void build(int lft,int rht,int ind) { tree[ind].lft=lft; tree[ind].rht=rht; tree[ind].init(); if(lft!=rht) { int mid=tree[ind].mid(); build(lft,mid,LL(ind)); build(mid+1,rht,RR(ind)); } } void updata(int st,int ed,int ind) { int lft=tree[ind].lft,rht=tree[ind].rht; if(st<=lft&&rht<=ed) tree[ind].fun(); else { down(ind); int mid=tree[ind].mid(); if(st<=mid) updata(st,ed,LL(ind)); if(ed> mid) updata(st,ed,RR(ind)); tree[ind].cnt=tree[LL(ind)].cnt+tree[RR(ind)].cnt; } } }seg; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { seg.build(1,n,1); for(int i=0;i<m;i++) op[i].get(); sort(op,op+m); int mx=0,cnt=seg.tree[1].cnt; for(int i=0;i<m;i++) { seg.updata(op[i].st+1,op[i].ed-1,1); mx=max(mx,cnt-seg.tree[1].cnt+2); cnt=seg.tree[1].cnt; } printf("%d\n",max(mx,seg.tree[1].cnt)); } return 0; }