POJ 3667セグメントツリーの区間マージの簡単な問題
17042 ワード
番号1-Nの部屋が并んでいます.操作1:連続長さaの空き部屋があるかどうかを尋ねる、ある場合は一番左(a部屋占有)に入る操作2:[a,a+b-1]の部屋を空ける(b部屋を空ける)考え方:各区間の「左寄り」「右寄り」「真ん中」の空き部屋線分を記録する操作:update:区間置換query:条件を満たす一番左の端点を尋ねる
タイトルリンク:
http://vjudge.net/problem/viewProblem.action?id=10354
タイトル操作:
ここは一番左から住む部屋を探しているので、ここは通常のquery関数のように書くことができず、やっと自分がテンプレートをセットするしかない末路の悲しみに気づいた.
そしてあなたはquery関数で、できるだけ左の部屋を探すので、左から先に再帰します.
1.
int query(int cur,int x,int y,int w){ int mid=(x+y)>>1,ls=cur<<1,rs=cur<<1|1; if(x==y) return x; //ここでは木の底の葉のないノードが見つかったら関数を終了することを示すとともに,点が見つからないことを防止するが,実際にはここで求めた点が見つからないと,右のサブツリーに入って最大のサブノードに戻ってくる. pushdown(cur,x,y); if(mc[cur<<1]>=w) return query(ls,x,mid,w); //左側に満たされた点が見つかれば、私たちは絶えず左側に向かって再帰します. Else if(rc[cur<<1]+lc[cur<<1|1]>=w)return mid-rc[cur<<1]+1;//左側が成り立たない真ん中を探して一緒に形成した部屋の一番左側の点を探し始めます return query(rs,mid+1,y,w); //左側中央が成立しない場合は右サブツリーに入ってポイントを探すしかありません}このquery関数には必ず戻り値があるので、メイン関数で適切な一連の部屋が見つかるかどうかを判断してからans=query(1,1,n,w)操作と後ろの部屋の入居のカバー操作を行わなければなりません.
この判断は単純1が線分樹根ノードであるため、mc[1]は実は最大の連続最長部屋であり、if(mc[1]>=w)という判断を実行すればよい
ここでputs(「0」):puts()関数は、標準出力装置(スクリーン)に文字列を書き、改行するために使用され、puts(s)が呼び出される.ここで、sは文字列文字(文字列はいれつ名または文字列ししん)である.
だからこの問題puts(「0」);存在しない場合を出力する
2.
もちろん、queryの関数の中で小さな修正をして、部屋が見つからないときに-1を出力することもできます.
int query(int cur,int x,int y,int w){ int mid=(x+y)>>1,ls=cur<<1,rs=cur<<1|1; if(x==y)return mc[cur]=w) return query(ls,x,mid,w); else if(rc[cur<<1]+lc[cur<<1|1]>=w) return mid-rc[cur<<1]+1; return query(rs,mid+1,y,w);}
総コードは次のとおりです.
タイトルリンク:
http://vjudge.net/problem/viewProblem.action?id=10354
タイトル操作:
ここは一番左から住む部屋を探しているので、ここは通常のquery関数のように書くことができず、やっと自分がテンプレートをセットするしかない末路の悲しみに気づいた.
そしてあなたはquery関数で、できるだけ左の部屋を探すので、左から先に再帰します.
1.
int query(int cur,int x,int y,int w){ int mid=(x+y)>>1,ls=cur<<1,rs=cur<<1|1; if(x==y) return x; //ここでは木の底の葉のないノードが見つかったら関数を終了することを示すとともに,点が見つからないことを防止するが,実際にはここで求めた点が見つからないと,右のサブツリーに入って最大のサブノードに戻ってくる. pushdown(cur,x,y); if(mc[cur<<1]>=w) return query(ls,x,mid,w); //左側に満たされた点が見つかれば、私たちは絶えず左側に向かって再帰します. Else if(rc[cur<<1]+lc[cur<<1|1]>=w)return mid-rc[cur<<1]+1;//左側が成り立たない真ん中を探して一緒に形成した部屋の一番左側の点を探し始めます return query(rs,mid+1,y,w); //左側中央が成立しない場合は右サブツリーに入ってポイントを探すしかありません}このquery関数には必ず戻り値があるので、メイン関数で適切な一連の部屋が見つかるかどうかを判断してからans=query(1,1,n,w)操作と後ろの部屋の入居のカバー操作を行わなければなりません.
この判断は単純1が線分樹根ノードであるため、mc[1]は実は最大の連続最長部屋であり、if(mc[1]>=w)という判断を実行すればよい
ここでputs(「0」):puts()関数は、標準出力装置(スクリーン)に文字列を書き、改行するために使用され、puts(s)が呼び出される.ここで、sは文字列文字(文字列はいれつ名または文字列ししん)である.
だからこの問題puts(「0」);存在しない場合を出力する
2.
もちろん、queryの関数の中で小さな修正をして、部屋が見つからないときに-1を出力することもできます.
int query(int cur,int x,int y,int w){ int mid=(x+y)>>1,ls=cur<<1,rs=cur<<1|1; if(x==y)return mc[cur]
総コードは次のとおりです.
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 #define N 50010
6 #define L ls,x,mid
7 #define R rs,mid+1,y
8 int rev[N<<2],lc[N<<2],rc[N<<2],mc[N<<2];
9 void update(int cur,int x,int y)
10 {
11 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
12 lc[cur]=lc[ls],rc[cur]=rc[rs];
13 mc[cur]=max(mc[ls],mc[rs]);
14 mc[cur]=max(mc[cur],rc[ls]+lc[rs]);
15 if(lc[ls]==mid-x+1) lc[cur]=lc[ls]+lc[rs];
16 if(rc[rs]==y-mid) rc[cur]=rc[rs]+rc[ls];
17 }
18 void build(int cur,int x,int y)
19 {
20 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
21 rev[cur]=-1;
22 if(x==y){
23 lc[cur]=rc[cur]=mc[cur]=1;
24 return;
25 }
26 build(ls,x,mid);
27 build(rs,mid+1,y);
28 update(cur,x,y);
29 }
30 void pushdown(int cur,int x,int y)
31 {
32 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
33 if(rev[cur]!=-1){
34 if(rev[cur]==1){
35 rev[ls]=rev[rs]=1;
36 lc[ls]=rc[ls]=mc[ls]=lc[rs]=rc[rs]=mc[rs]=0;
37 rev[cur]=-1;
38 }
39 else if(rev[cur]==0){
40 rev[ls]=rev[rs]=0;
41 lc[ls]=rc[ls]=mc[ls]=mid-x+1;
42 lc[rs]=rc[rs]=mc[rs]=y-mid;
43 rev[cur]=-1;
44 }
45 }
46 }
47 void change(int cur,int x,int y,int s,int t,int v)
48 {
49 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
50 if(x>=s&&y<=t){
51 rev[cur]=v;
52 lc[cur]=rc[cur]=mc[cur]=v?0:y-x+1;
53 return;
54 }
55 pushdown(cur,x,y);
56 if(mid>=s) change(ls,x,mid,s,t,v);
57 if(mid+1<=t) change(rs,mid+1,y,s,t,v);
58 update(cur,x,y);
59 }
60 int query(int cur,int x,int y,int w)
61 {
62 int mid=(x+y)>>1,ls=cur<<1,rs=cur<<1|1;
63 if(x==y) return x;
64 pushdown(cur,x,y);
65 if(mc[cur<<1]>=w) return query(ls,x,mid,w);
66 else if(rc[cur<<1]+lc[cur<<1|1]>=w) return mid-rc[cur<<1]+1;
67 return query(rs,mid+1,y,w);
68 }
69 int main()
70 {
71 int n,m,op,a,b;
72 while(scanf("%d%d",&n,&m)!=EOF){
73 build(1,1,n);
74 for(int i=0;i<m;i++){
75 scanf("%d",&op);
76 if(op==1){
77 scanf("%d",&a);
78 if(mc[1]<a) puts("0");
79 else{
80 int ans=query(1,1,n,a);
81 printf("%d
",ans);
82 change(1,1,n,ans,ans+a-1,1);
83 }
84 }
85 else{
86 scanf("%d%d",&a,&b);
87 change(1,1,n,a,a+b-1,0);
88 }
89 }
90 }
91 return 0;
92 }