》》》算法竞赛

/**
 * @file            
 * @author          jUicE_g2R(qq:3406291309)————彬(bin-必应)
 *						一个某双流一大学通信与信息专业大二在读	
 * 
 * @brief           一直在算法竞赛学习的路上
 * 
 * @copyright       2023.9
 * @COPYRIGHT			 原创技术笔记：转载需获得博主本人同意，且需标明转载源
 *
 * @language        C++
 * @Version         1.0还在学习中  
 */

• UpData Log👆 2023.9.11 更新进行中
• Statement0🥇 一起进步
• Statement1💯 有些描述可能不够标准，但能达其意

技术提升站点

17-2 使用 线段树 实现 区间合并

为何线段树很容易实现区间合并？

线段树 的兄弟节点之间有相邻关系

在合并区间时，只需要根节点向子树方向延展即可确定相邻的区间。

HDU 1540 地道战

问题描述：

在一条线上有连续的 n 个村庄 ，相邻之间用地道连接。做 m 次操作，n，m<=50000

操作有 3 种：

1）D x ，第 x 个村庄被毁，它的地道随之毁灭

2）Q x，查询第 x 个村庄能到达的村庄总数（包括村庄 x）

3）R ，重建刚才被毁的村庄

• 思路展示

将所有村庄的状态初始化为 1 （即未被毁灭），且他们连在一起是一个完整连续的区间。被毁后状态值改变为 0 。

该题求 能到达村庄的个数 实际上求 队列上 包含该村庄的 连续为 1 的区间。第 x 个村庄能到达的村庄分为左抵达与右抵达。

用到的是 线段树 的 单点修改+区间查询解题。

线段树现在需要维护两个参数：

1）一个就前缀最长 1 序列，从区间左端点开始向右的最大连续个数，用pre[]记录

1）另一个就后缀最长 1 序列，从区间右端点开始向左的最大连续个数，用suf[]记录

• 代码展示

#include<bits/stdc++.h>
using namespace std;
const int N=5E5+10;
vector<int> tree(N<<2,1);                         	//初始化为未被摧毁：1
vector<int> pre(N<<2,0);                          	//前缀1的个数
vector<int> suf(N<<2,0);                          	//后缀1的个数
vector<int> Destory_History(N,0);                	//村庄被毁日志
int d_id;                                           //被毁村庄的编号
int ls(int id){return id<<1;}                       //获取左子节点的编号 id*2
int rs(int id){return id<<1|1;}                     //获取左子节点的编号 id*2+1
/*Build_Tree是自上而下的架构子节点（分配区间），Get_Parent是利用架构好的结构将下面的值向上合并返回*/
void Get_Parent(int p,int len){
    //将下边子节点的值向上面的父节点传递
    pre[p]=pre[ls(p)];
    suf[p]=suf[rs(p)];
    //【len>>1：len/2】
    if(pre[ls(p)] == (len-(len>>1)))                //当前父节点的左子节点的区间全是1（没一座村庄被毁灭）
        pre[p] = pre[ls(p)] + pre[rs(p)];
    if(suf[rs(p)] == (len>>1))
        suf[p] = suf[ls(p)] + suf[rs(p)];
}
void Build_Tree(int p,int L,int R){			        //父节点以及他的左右端点值
    if(L==R){                                       //当左右端点相等时就是（最底层的）叶子节点
        pre[p]=suf[p]=1;   
        return;
    }	
    int mid=(L+R)>>1;					            //分治思想：折半查找
    Build_Tree(ls(p),       L, mid);                //（向下递归）左子节点
    Build_Tree(rs(p),   mid+1,   R);                //（向下递归）右子节点
    Get_Parent(    p,(R-L+1));					    //（自下而上）传递区间值
}
void Updata(int p,int L,int R){
    if(L==R){                                       //当左右端点相等时就是（最底层的）叶子节点
        tree[p]=pre[p]=suf[p]=0;                    //查找到被摧毁的村庄了，更新叶子结点的状态值
        return;
    }
    //不断向下递归查找到被摧毁的村庄
    int mid=(L+R)>>1;
    if(d_id<=mid)
        Updata(ls(p),       L, mid);
    else
        Updata(rs(p),   mid+1,   R);
    //通过栈，自下而上的将沿途的父节点的值修改掉    
    Get_Parent(    p,(R-L+1));                      
}
int Query(int p,int L,int R){
    if(L==R)
        return tree[p];
    int mid=(L+R)>>1;
    if(d_id<=mid){                                  //被毁村庄在左子树上
        if(d_id + suf[ls(p)] > mid) 
            return (suf[ls(p)] + pre[rs(p)]);
        else                    
            return Query(ls(p),     L, mid);
    }
    else{                                           //被毁村庄在右子树上
        if(mid + pre[rs(p)] >= d_id) 
            return (pre[ls(p)] + suf[rs(p)]);
        else                    
            return Query(rs(p), mid+1,  R);
    }
}

• 优化：结构体集束化数据

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> Destory_History(N,0);
int d_id;
struct node{
    int p, ls=p<<1, rs=(p<<1|1); 
    int lsum, rsum, sum;
    int L, R, mid=L+(R-L)/2, len=(R-L+1);
    node(int p,int L,int R):p(p),L(L),R(R){}
} n[N<<2];//(N<<2) = 4N
void Get_Parent(int p){                                         //p对应的是n[p]这个结点
    n[p].lsum=n[ n[p].ls ].lsum;
    n[p].rsum=n[ n[p].rs ].rsum;
    if(n[ n[p].ls ].lsum == n[ n[p].ls ].len)                   //左子节点的区间全是1（没一座村庄被毁灭）
        n[p].lsum = n[ n[p].ls ].lsum + n[ n[p].rs ].lsum;
    if(n[ n[p].rs ].lsum == n[ n[p].rs ].len)                   //右子节点的区间全是1（没一座村庄被毁灭）
        n[p].rsum = n[ n[p].ls ].rsum + n[ n[p].rs ].rsum;
    //n[p].sum = max(n[p].lsum, max(n[p].rsum, n[ n[p].ls ].rsum + n[ n[p].rs ].lsum));
}
void Build_Tree(int p,int L,int R){
    n[p].L=L;       n[p].R=R;
    int mid=n[p].mid;
    if(L==R){
        n[p].lsum=n[p].rsum=n[p].len=1; 
        return;
    }
    Build_Tree(n[p].ls,     L, mid);
    Build_Tree(n[p].rs, mid+1,   R);
    Get_Parent(p);
}
void Updata(int p){
    if(n[p].L == n[p].R){                                       
        n[p].lsum=n[p].rsum=n[p].sum=0;                    
        return;
    }
    if(d_id<=n[p].mid)
        Updata(n[p].ls);
    else
        Updata(n[p].rs);
    //通过栈，自下而上的将沿途的父节点的值修改掉    
    Get_Parent(p);                      
}

• 补充说明

结构体中可以写成函数形式，但考虑到函数中返回的这些参数是常用的就直接存储在结构体数组中而无需多次调用计算（费时），故没有采取这种方法

struct node{
    int p;
    int lsum, rsum;
    int L, R;
    int ls(void) {return p<<1;}
    int rs(void) {return p<<1|1;}
    int mid(void){return L+(R-L)>>1}				//避免溢出
    //int mid(void){return (L+R)>>1}
    int len(void){return (R-L+1)}
    node(int p,int L,int R):p(p),L(L),R(R){}
} n[N<<2];//(N<<2) = 4N