經典的區間合并題。
參考這篇文章學習的，
http://www.notonlysuccess.com/?p=978以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/4 18:38:40
* File Name: poj3667.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-11);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(50007);
struct Node
{
int a,b;
int max,lmax,rmax;
bool cover;
};
int n,m;
Node tree[kMaxn<<2];
void Build(int node,int x,int y)
{
tree[node].a=x;
tree[node].b=y;
tree[node].max=tree[node].lmax=tree[node].rmax=y-x+1;
tree[node].cover=false;
if(x<y)
{
int m(Half(x+y));
Build(L(node),x,m);
Build(R(node),m+1,y);
}
}
void PushDown(int node)
{
if(!tree[node].cover)
return;
tree[node].cover=false;
tree[L(node)].cover=tree[R(node)].cover=true;
if(tree[node].max)
{
tree[L(node)].max=tree[L(node)].lmax=tree[L(node)].rmax=tree[L(node)].b-tree[L(node)].a+1;
tree[R(node)].max=tree[R(node)].lmax=tree[R(node)].rmax=tree[R(node)].b-tree[R(node)].a+1;
}
else
{
tree[L(node)].max=tree[L(node)].lmax=tree[L(node)].rmax=0;
tree[R(node)].max=tree[R(node)].lmax=tree[R(node)].rmax=0;
}
}
void PushUp(int node)
{
tree[node].max=max(tree[L(node)].max,tree[R(node)].max);
tree[node].max=max(tree[node].max,tree[L(node)].rmax+tree[R(node)].lmax);
if(tree[L(node)].max==tree[L(node)].b-tree[L(node)].a+1)
tree[node].lmax=tree[L(node)].max+tree[R(node)].lmax;
else
tree[node].lmax=tree[L(node)].lmax;
if(tree[R(node)].max==tree[R(node)].b-tree[R(node)].a+1)
tree[node].rmax=tree[L(node)].rmax+tree[R(node)].max;
else
tree[node].rmax=tree[R(node)].rmax;
}
void Modify(int node,int x,int y,int sign)
{
int len(tree[node].b-tree[node].a+1);
if(x<=tree[node].a && tree[node].b<=y)
{
tree[node].cover=true;
if(sign==0)
tree[node].max=0;
else
tree[node].max=len;
tree[node].lmax=tree[node].rmax=tree[node].max;
return;
}
PushDown(node);
int m(Half(tree[node].a+tree[node].b));
if(m>=x)
Modify(L(node),x,y,sign);
if(m<y)
Modify(R(node),x,y,sign);
PushUp(node);
}
int Query(int node,int need)
{
if(tree[node].max<need)
return 0;
if(tree[node].a==tree[node].b)
return tree[node].a;
PushDown(node);
if(tree[node].lmax>=need)
return tree[node].a;
if(tree[L(node)].max>=need)
return Query(L(node),need);
if(tree[L(node)].rmax+tree[R(node)].lmax>=need)
return tree[L(node)].b-tree[L(node)].rmax+1;
return Query(R(node),need);
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d%d",&n,&m)==2)
{
Build(1,1,n);
while(m--)
{
int cmd;
scanf("%d",&cmd);
if(cmd==1)
{
int a,result;
scanf("%d",&a);
result=Query(1,a);
printf("%d\n",result);
if(result)
Modify(1,result,result+a-1,0);
}
else
{
int a,b;
scanf("%d%d",&a,&b);
Modify(1,a,a+b-1,1);
}
}
}
return 0;
}
posted on 2011-08-17 20:02
lee1r 閱讀(651)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構