题目链接http://poj.org/problem?id3667题目大意思路大概就是线段树的区间合并ACCode#includestdlib.h #includestring.h #includestdio.h #includetime.h #includemath.h // srand(unsigned)time(NULL));rand(); #includemap #includeset #includedeque #includequeue #includestack #includebitset #includestring #includefstream #includeiostream #includealgorithm #define ll long long #define Pair pairint,int #define clean(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXN1e510; const int INF320x3f3f3f3f; const ll INF640x3f3f3f3f3f3f3f3f; const ll MOD1e97; const double PIacos(-1.0); const double EPS1.0e-8; //unsigned register // ios::sync_with_stdio(false) struct SegTree{ struct Node{ int l,r; int ls,rs,ms; int Lazy; }; Node Tree[MAXN2]; void PushDown(int rt){ if(Tree[rt].Lazy!-1){ Tree[rt1].LazyTree[rt1|1].LazyTree[rt].Lazy; Tree[rt1].lsTree[rt1].rsTree[rt1].msTree[rt].Lazy?0:Tree[rt1].r-Tree[rt1].l1; Tree[rt1|1].lsTree[rt1|1].rsTree[rt1|1].msTree[rt].Lazy?0:Tree[rt1|1].r-Tree[rt1|1].l1; Tree[rt].Lazy-1; } } void PushUp(int rt){ //线段树合并 Tree[rt].lsTree[rt1].ls; Tree[rt].rsTree[rt1|1].rs; int mid(Tree[rt].lTree[rt].r)1;//中间节点 if(Tree[rt].lsmid-Tree[rt].l1) Tree[rt].lsTree[rt1|1].ls;//整个左子节点都覆盖了 if(Tree[rt].rsTree[rt].r-mid) Tree[rt].rsTree[rt1].rs;//整个右子节点都被覆盖了 Tree[rt].msmax(max(Tree[rt1].ms,Tree[rt1|1].ms),Tree[rt1].rsTree[rt1|1].ls); } void Build(int l,int r,int rt){ Tree[rt].ll;Tree[rt].rr; Tree[rt].lsTree[rt].rsTree[rt].msr-l1; Tree[rt].Lazy-1; if(lr) return ; int mid(lr)1; Build(l,mid,rt1);Build(mid1,r,rt1|1); } void Update(int ql,int qr,int val,int rt){ if(Tree[rt].lqlTree[rt].rqr){ Tree[rt].Lazyval; Tree[rt].lsTree[rt].rsTree[rt].msval?0:qr-ql1; return ; }PushDown(rt); int mid(Tree[rt].lTree[rt].r)1; if(qrmid) Update(ql,qr,val,rt1); else if(qlmid) Update(ql,qr,val,rt1|1); else{ Update(ql,mid,val,rt1); Update(mid1,qr,val,rt1|1); }PushUp(rt); } int Query(int ql,int qr,int val,int rt){ if(qlqr) return ql; PushDown(rt); int mid(qlqr)1; if(Tree[rt1].msval) return Query(ql,mid,val,rt1); else if(Tree[rt1].rsTree[rt1|1].lsval) return mid-Tree[rt1].rs1; return Query(mid1,qr,val,rt1|1); } void Show(int rt){ printf(ls%d rs%d ms%d Lazy%d\n,Tree[rt].ls,Tree[rt].rs,Tree[rt].ms,Tree[rt].Lazy); if(Tree[rt].lTree[rt].r) return ; Show(rt1);Show(rt1|1); } }; SegTree Seg; int n,m; int main(){ scanf(%d%d,n,m); Seg.Build(1,n,1); //Seg.Show(1);puts(); while(m--){ int opt;scanf(%d,opt); if(opt1){ int a;scanf(%d,a); if(Seg.Tree[1].msa) printf(0\n); else{ int AnsSeg.Query(1,n,a,1); printf(%d\n,Ans); Seg.Update(Ans,Ansa-1,1,1); } } else{ int a,b;scanf(%d%d,a,b); Seg.Update(a,ab-1,0,1); } //Seg.Show(1);puts(); } }