生活随笔
收集整理的這篇文章主要介紹了
洛谷T44252 线索_分治线段树_思维题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
分治線段樹，其實就是將標(biāo)記永久化，到最后再統(tǒng)一下傳所有標(biāo)記。
至于先后順序，可以給每個節(jié)點開一個時間戳。
一般地，分治線段樹用于離線，只查詢一次答案的題目。
本題中，標(biāo)記要被下傳 222 次。
Code：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std
;
const int maxn
= 100000 + 10;
int n
,m
, tag
[maxn
<< 2], lazy
[maxn
<< 2], siz
[maxn
], root
[maxn
], p
[maxn
], tag_root
[maxn
], ans
[maxn
];
int find(int x
){ return p
[x
] == x
? x
: p
[x
] = find(p
[x
]); }
struct Segment_Tree
{# define lson (o << 1)# define rson (o << 1)|1 void update(int l
, int r
, int L
, int R
, int col
, int times
, int o
) {if(l
> r
|| r
< L
|| l
> R
) return ;if(l
>= L
&& r
<= R
){lazy
[o
] = col
, tag
[o
] = times
;return;}int mid
= (l
+ r
) >> 1;update(l
, mid
, L
, R
,col
, times
, lson
);update(mid
+ 1, r
, L
, R
, col
, times
, rson
);}inline void pushdown(int o
){if(tag
[o
] > tag
[lson
]) lazy
[lson
] = lazy
[o
], tag
[lson
] = tag
[o
]; if(tag
[o
] > tag
[rson
]) lazy
[rson
] = lazy
[o
], tag
[rson
] = tag
[o
];}void release(int o
, int l
, int r
){if(l
> r
) return ;if(l
== r
){int x
= find(l
);if(tag_root
[x
] > tag
[o
])ans
[l
] = root
[x
];else ans
[l
] = lazy
[o
], tag_root
[x
] = tag
[o
], root
[x
] = lazy
[o
];return ;}int mid
= (l
+ r
) >> 1;pushdown(o
);release(lson
, l
, mid
);release(rson
, mid
+ 1, r
);}
}T
;
int main()
{scanf("%d%d",&n
,&m
);for(int i
= 1;i
<= n
; ++i
) { int c
; scanf("%d",&c
);p
[i
] = i
, root
[i
] = c
, siz
[i
] = 1, tag_root
[i
] = 1;} for(int i
= 2;i
<= m
+ 1; ++i
){ int opt
, l
, r
, x
; scanf("%d%d%d%d",&opt
,&l
,&r
,&x
); switch(opt
) {case 1:T
.update(1, n
, l
, r
, x
, i
, 1);break;case 2:int a
= find(l
), b
= find(r
);root
[b
] = x
, tag_root
[b
] = i
;if(a
!= b
) { p
[a
] = b
, siz
[b
] += siz
[a
]; }break;}}T
.release(1, 1, n
);T
.release(1, 1, n
);for(int i
= 1;i
<= n
; ++i
) printf("%d ",ans
[i
]);printf("\n");for(int i
= 1;i
<= n
; ++i
){int x
= find(i
);printf("%d ",siz
[x
] - 1);}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/guangheli/p/9845113.html
總結(jié)
以上是生活随笔為你收集整理的洛谷T44252 线索_分治线段树_思维题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
