企业官网建设流程全解析

题目链接：http://poj.org/problem?id=3667

题目大意：

思路：大概就是线段树的区间合并

ACCode：

#include<stdlib.h> #include<string.h> #include<stdio.h> #include<time.h> #include<math.h> // srand(unsigned)time(NULL));rand(); #include<map> #include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<string> #include<fstream> #include<iostream> #include<algorithm> #define ll long long #define Pair pair<int,int> #define clean(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXN=1e5+10; const int INF32=0x3f3f3f3f; const ll INF64=0x3f3f3f3f3f3f3f3f; const ll MOD=1e9+7; const double PI=acos(-1.0); const double EPS=1.0e-8; //unsigned register // ios::sync_with_stdio(false) struct SegTree{ struct Node{ int l,r; int ls,rs,ms; int Lazy; }; Node Tree[MAXN<<2]; void PushDown(int rt){ if(Tree[rt].Lazy!=-1){ Tree[rt<<1].Lazy=Tree[rt<<1|1].Lazy=Tree[rt].Lazy; Tree[rt<<1].ls=Tree[rt<<1].rs=Tree[rt<<1].ms=Tree[rt].Lazy?0:Tree[rt<<1].r-Tree[rt<<1].l+1; Tree[rt<<1|1].ls=Tree[rt<<1|1].rs=Tree[rt<<1|1].ms=Tree[rt].Lazy?0:Tree[rt<<1|1].r-Tree[rt<<1|1].l+1; Tree[rt].Lazy=-1; } } void PushUp(int rt){ //线段树合并 Tree[rt].ls=Tree[rt<<1].ls; Tree[rt].rs=Tree[rt<<1|1].rs; int mid=(Tree[rt].l+Tree[rt].r)>>1;//中间节点 if(Tree[rt].ls==mid-Tree[rt].l+1) Tree[rt].ls+=Tree[rt<<1|1].ls;//整个左子节点都覆盖了 if(Tree[rt].rs==Tree[rt].r-mid) Tree[rt].rs+=Tree[rt<<1].rs;//整个右子节点都被覆盖了 Tree[rt].ms=max(max(Tree[rt<<1].ms,Tree[rt<<1|1].ms),Tree[rt<<1].rs+Tree[rt<<1|1].ls); } void Build(int l,int r,int rt){ Tree[rt].l=l;Tree[rt].r=r; Tree[rt].ls=Tree[rt].rs=Tree[rt].ms=r-l+1; Tree[rt].Lazy=-1; if(l==r) return ; int mid=(l+r)>>1; Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1); } void Update(int ql,int qr,int val,int rt){ if(Tree[rt].l==ql&&Tree[rt].r==qr){ Tree[rt].Lazy=val; Tree[rt].ls=Tree[rt].rs=Tree[rt].ms=val?0:qr-ql+1; return ; }PushDown(rt); int mid=(Tree[rt].l+Tree[rt].r)>>1; if(qr<=mid) Update(ql,qr,val,rt<<1); else if(ql>mid) Update(ql,qr,val,rt<<1|1); else{ Update(ql,mid,val,rt<<1); Update(mid+1,qr,val,rt<<1|1); }PushUp(rt); } int Query(int ql,int qr,int val,int rt){ if(ql==qr) return ql; PushDown(rt); int mid=(ql+qr)>>1; if(Tree[rt<<1].ms>=val) return Query(ql,mid,val,rt<<1); else if(Tree[rt<<1].rs+Tree[rt<<1|1].ls>=val) return mid-Tree[rt<<1].rs+1; return Query(mid+1,qr,val,rt<<1|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].l==Tree[rt].r) return ; Show(rt<<1);Show(rt<<1|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(opt==1){ int a;scanf("%d",&a); if(Seg.Tree[1].ms<a) printf("0\n"); else{ int Ans=Seg.Query(1,n,a,1); printf("%d\n",Ans); Seg.Update(Ans,Ans+a-1,1,1); } } else{ int a,b;scanf("%d%d",&a,&b); Seg.Update(a,a+b-1,0,1); } //Seg.Show(1);puts(""); } }