HDU 1540 Tunnel Warfare
题目传送门 HDU 1540 Tunnel Warfare
这道题题意是刚开始有n个点，每个点都与其左右相连，有三种操作
- 将一个点破坏，那么该点的左右两点就不连通了
- 恢复上一个破坏的点，恢复联通性
- 查询一个与一个点联通的个数
这道题是一个直接来看是单点修改，单点查询。
先说第一种做法
线段树维护区间从左端点开始连续的最大值，从右端点开始连续的最大值
lmax表示从左端点开始连续的最大值，rmax表示从右端点开始连续的最大值
- 在pushup的时候，如果左儿子的lmax等于左儿子的区间长度，那么该节点的lmax = 左儿子的lmax + 右儿子的lmax，否则等于左儿子的lmax
- 同样的 ，如果右儿子的rmax等于右儿子区间长度，那么该节点的rmax = 右儿子的rmax + 左儿子的rmax ，否则等于右儿子的rmax
- 在modify(修改)的时候，如果被破坏就将该点的lmax和rmax都置为0
- 在query(查询)的时候，在左区间，如果该点在左区间的rmax内，则返回左儿子的rmax + 右儿子的lmax ，否则递归左儿子处理
- 在右区间，如果该点在右区间的lmax内，则返回左儿子的rmax + 右儿子的lmax ，否则递归右儿子处理。
- 查询到长度是1的区间直接返回lmax或者rmax
参考代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e4 + 100 ;
int n,m;
vector<int> v; //记录每次破坏的点的id，来恢复点的时候使用
struct node //线段树
{
int l,r,lmax,rmax ;
}tr[N * 4];
void pushup(int u){ //更新
tr[u].lmax = tr[u << 1].lmax ; // lmax等于左儿子的lmax
if(tr[u<<1].lmax == tr[u << 1].r - tr[u << 1].l + 1){ //如果左儿子的lmax等于其区间长度，那么lmax等于 左儿子lmax + 右儿子lmax
tr[u].lmax = tr[u << 1].lmax + tr[u << 1| 1].lmax ;
}
tr[u].rmax = tr[u << 1|1].rmax ; // rmax 等于右儿子的rmax
if(tr[u << 1 | 1].rmax == tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1){ // 如果右儿子的rmax等于其区间长度，那么rmax等于 左儿子的rmax + 右儿子的rmax
tr[u].rmax = tr[u << 1 | 1 ].rmax + tr[u << 1 ].rmax ;
}
}
void build(int u,int l,int r){
tr[u] = {l,r,1,1} ; //初始化端点存在，所以lmax=rmax = 1
if(l != r){
int mid = l + r >> 1;
build(u << 1 ,l , mid) ,build(u << 1 | 1 ,mid + 1 , r) ;
pushup(u) ;
}
}
void modify(int u,int x,int ans){ //修改操作
if(tr[u].l == tr[u].r && tr[u].l == x){
tr[u].lmax = tr[u].rmax = ans ;
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1 , x, ans) ;
if(x >= mid + 1)modify(u << 1| 1,x,ans) ;
pushup(u) ;
}
}
int query(int u,int x){ //查询操作
if(tr[u].l == x&& tr[u].r == x){
return tr[u].lmax ;
}
int mid = tr[u].l + tr[u].r >> 1;
int ans = 0 ;
if(x <= mid){
if(x >= tr[u << 1].r - tr[u << 1].rmax + 1 ) return tr[u<<1].rmax + tr[u << 1 | 1].lmax ; //x在左区间的rmax中
else ans = query(u << 1 ,x) ; //递归左儿子处理
}
else if(x >= mid + 1 ){
if(x <= mid + 1 + tr[u << 1 | 1].lmax - 1 ) return tr[u << 1 | 1].lmax + tr[u<< 1].rmax ; //x在右区间的lmax中
else ans = query(u << 1 | 1,x) ; //递归右儿子处理
}
return ans ;
}
int main(){
ios::sync_with_stdio(false) ;
cin.tie(0) ;
cout.tie(0) ;
while(cin >> n >> m){
build(1,1,n) ;
while(m--){
char op;
int x ;
cin >> op ;
if(op == 'D'){
cin >> x;
v.push_back(x) ; //记录被摧毁的点
modify(1,x,0) ;
}
else if(op == 'R'){
int t = v.back() ;
v.pop_back() ;
modify(1,t,1) ;
}
else{
cin >> x ;
cout << query(1,x) << "\n" ;
}
}
}
return 0;
}
方法二
只维护被破坏的村庄的id
假设
村庄是否被破坏 0 1 0 0 0 0 0 1 0 （1代表被破坏）
村庄的编号 1 2 3 4 5 6 7 8 9
那么当查询4在的联通的个数可以查询1 ~ 4 的被破坏村庄的id最大值maxw = 1， ，4 ~ n 的被破坏村庄的id的最小值minw = 8
那么minw - maxw - 1就是联通个数
就是每个线段维护该线段的最大值和最小值，如果一个点被摧毁，那么该点值置为id，没有被摧毁没有值
那么初始化的时候应该将每个区间的minw置为n+1，最大值置为 0，（因为在可以看作0和n+1都有村庄，只不过在一开始就被破坏）
特殊情况
村庄是否被破坏 0 0 0 0 1 0 0 0 0 （1代表被破坏）
村庄的编号 1 2 3 4 5 6 7 8 9
如果所查询5村庄已被破坏，那么 查询的minw 和 maxw都是 该5，要特判，输出0
这时就变成了单点修改区间查询
查询x时，先查询1 ~ x 中最大值 maxw，再查询x ~ n 的最小值 minw ，
如果 minw == maxw 输出 0 ，， 否则 输出 minw - maxw - 1 ；
那么就是区间最大最小值模型了
参考代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int N = 5e4 + 100, INF = 1e9 ;
int n,m;
struct node
{
int l,r,minw,maxw; //维护区间的最大值和最小值
}tr[N * 4];
vector<int> v ;
void pushup(int u){
tr[u].minw = min(tr[u << 1].minw , tr[u << 1 | 1].minw) ;
tr[u].maxw = max(tr[u << 1].maxw , tr[u << 1 | 1].maxw) ;
}
void build(int u,int l,int r){
tr[u] = {l,r,n + 1 ,0} ;
if(l != r){
int mid = l + r >> 1;
build(u << 1, l ,mid) , build(u << 1 | 1,mid + 1 ,r) ;
pushup(u) ;
}
}
void modify(int u ,int idx,int x){
if(tr[u].l == idx && tr[u].r == idx){
if(x){
tr[u].maxw = tr[u].minw = x ;
}
else{
tr[u].minw = n + 1 ;
tr[u].maxw = 0 ;
}
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(idx <= mid ) modify(u << 1 ,idx,x) ;
if(idx >= mid + 1 ) modify(u << 1 | 1 ,idx,x) ;
pushup(u) ;
}
}
int query_min(int u,int l,int r){ //查询最小值
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].minw ;
}
int mid = tr[u].l + tr[u].r >> 1;
int ans = INF ;
if(l <= mid ) ans = query_min(u << 1 , l , r) ;
if(r >= mid + 1) ans = min(ans,query_min(u << 1 | 1 ,l,r)) ;
return ans ;
}
int query_max(int u,int l,int r){ //查询最大值
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].maxw ;
}
int mid = tr[u].l + tr[u].r >> 1 ;
int ans = 0 ;
if(l <= mid) ans = query_max(u << 1 , l ,r) ;
if(r >= mid + 1) ans= max(ans,query_max(u << 1 | 1 ,l, r)) ;
return ans ;
}
int main(){
ios::sync_with_stdio(false) ;
cin.tie(0) ;
cout.tie(0) ;
while(cin >> n >> m){
v.clear() ;
build(1,1,n) ;
while(m--){
char op ;
int x ;
cin >> op ;
if(op == 'D'){
cin >> x ;
v.push_back(x) ;
modify(1,x,x) ;
}
else if(op == 'R'){
int t = v.back() ;
v.pop_back() ;
modify(1,t,0) ;
}
else {
cin >> x ;
int maxw = query_max(1,1,x) ;
int minw = query_min(1,x,n) ;
if(minw == maxw){
cout << 0 << "\n" ;
}
else {
cout << minw - maxw - 1 << "\n" ;
}
}
}
}
return 0;
}
感谢提供思路fujang
方法三 就方法一是每次查询的时候查询1到x的rmax加上x到lmax，，这里由于x会计算两次，所以要减1
参考代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e4 + 100 ;
int n,m;
vector<int> v; //记录每次破坏的点的id，来恢复点的时候使用
struct node //线段树
{
int l,r,lmax,rmax ;
}tr[N * 4];
void pushup(int u){ //更新
tr[u].lmax = tr[u << 1].lmax ; // lmax等于左儿子的lmax
if(tr[u<<1].lmax == tr[u << 1].r - tr[u << 1].l + 1){ //如果左儿子的lmax等于其区间长度，那么lmax等于 左儿子lmax + 右儿子lmax
tr[u].lmax = tr[u << 1].lmax + tr[u << 1| 1].lmax ;
}
tr[u].rmax = tr[u << 1|1].rmax ; // rmax 等于右儿子的rmax
if(tr[u << 1 | 1].rmax == tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1){ // 如果右儿子的rmax等于其区间长度，那么rmax等于 左儿子的rmax + 右儿子的rmax
tr[u].rmax = tr[u << 1 | 1 ].rmax + tr[u << 1 ].rmax ;
}
}
void build(int u,int l,int r){
tr[u] = {l,r,1,1} ; //初始化端点存在，所以lmax=rmax = 1
if(l != r){
int mid = l + r >> 1;
build(u << 1 ,l , mid) ,build(u << 1 | 1 ,mid + 1 , r) ;
pushup(u) ;
}
}
void modify(int u,int x,int ans){ //修改操作
if(tr[u].l == tr[u].r && tr[u].l == x){
tr[u].lmax = tr[u].rmax = ans ;
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1 , x, ans) ;
if(x >= mid + 1)modify(u << 1| 1,x,ans) ;
pushup(u) ;
}
}
int query_rmax(int u,int l,int r){ //查询从l到r这个区间中rmax的值
if(tr[u].r == r && tr[u].l >= l) return tr[u].rmax ; //注意这里必须需要右端点相等才可，不能只是简单的包含区间
int mid = tr[u].l + tr[u].r >> 1 ;
int ans = 0 ;
if(r <= mid){ //代表查询区间全部在左边，直接递归处理左区间即可
ans = query_rmax(u<<1,l,r) ;
}
else if(l >= mid + 1) { //代表全部在右边，直接递归处理右半边即可
ans = query_rmax(u<<1|1,l,r) ;
}
else{ //代表查询区间两个子树都有
if(tr[u<<1|1].l + tr[u<<1|1].lmax - 1 >= r){ //代表右儿子的lmax包含r，，所以从右儿子到r是连续有值的，所以加上右面的然后2递归左儿子即可
ans = r - tr[u<<1|1].l + 1 + query_rmax(u<<1,l,mid) ;
}
else ans = query_rmax(u<<1|1,mid+1,r) ; //右面肯定不全部连续，所以只需递归右儿子即可
}
return ans ;
}
int query_lmax(int u,int l,int r){ //同rmax
if(tr[u].l == l && tr[u].r <= r) return tr[u].lmax ;
int mid = tr[u].l + tr[u].r >> 1 ;
int ans = 0 ;
if(r <= mid){
ans = query_lmax(u<<1,l,r) ;
}
else if(l >= mid + 1){
ans = query_lmax(u<<1|1,l,r) ;
}
else{
if(tr[u<<1].r - tr[u<<1].rmax + 1 <= l){
ans = tr[u<<1].r - l + 1 + query_lmax(u<<1|1,mid+1,r) ;
}
else ans = query_lmax(u<<1,l,mid) ;
}
return ans ;
}
int main(){
ios::sync_with_stdio(false) ;
cin.tie(0) ;
cout.tie(0) ;
while(cin >> n >> m){
build(1,1,n) ;
while(m--){
char op;
int x ;
cin >> op ;
if(op == 'D'){
cin >> x;
v.push_back(x) ; //记录被摧毁的点
modify(1,x,0) ;
}
else if(op == 'R'){
int t = v.back() ;
v.pop_back() ;
modify(1,t,1) ;
}
else{
cin >> x ;
//cout << query(1,x) << "\n" ;
int t = query_rmax(1,1,x) + query_lmax(1,x,n) ; //注意这里x计算了两次，，而且不能从1到x-1，因为这样x本身被摧毁就是错误的
if(t) t-- ; //所以需要减1，，当x本身就是被摧毁的化，就是0，所以不需要减
cout << t << "\n" ;
}
}
}
return 0;
}
想请教个问题 第一种方法 询问t位置的时候，为什么不能是当t为1时直接输出1到t-1的node的rmax加上t+1到n的lmax+1
可以这样写的，，感谢提供思路，，我按照你那种写了方法三可以看看。
但是不能写1到t-1，，这样的话当t本身被摧毁的化就是错误的，，，，应该求1到t的rmax和t到n的lmax，，这样当有村庄数的时候就减去重复计算的1即可
可以开个数组记录下是否被摧毁，如果被摧毁直接输出0，不然输出1到t-1和t+1到n
或者直接输出1到t的rmax和t到n的lmax 如果为0直接输出0，如果大于0则减一