题解：P5618 [SDOI2015] 道路修建

· · 题解

题意

两排点组成一个方格如下：

注意坐标顺序！

每条边有一个权值，给定初始权值，处理两种操作：

性质观察

发现以下性质：

  1. 每一段如果满足查询的要求（下称区间），必须有一条竖边；
  2. 将两区间合并时一定会加入两区间中的横边，在中间形成一个环（如下图，红线为左区间，绿色为右区间，紫色为新加入的横边，黄色区域即为环），要使合并后的段成为区间，我们删边能且只能在环中删除一条，可横可竖；

  1. 发现删除环中最大边一定能得到最优解。

思考

由以上性质，我们只需要维护以下区间内容：

  1. 每个区间最左及最右的竖边权值；

  1. 最左最右竖边左或者右边的最大横边权值；

  1. 整段的答案。

那么区间合并就会变得简单：

合并时去掉的权值最大的边很容易由左区间最右的竖边权值及其区间内右边横边最大值、右区间最左竖边权值及其区间内左边横边最大值、两段之间两条横边的权值得出。

新区间的答案即为左区间的答案、右区间的答案、两段之间两条横边的权值之和减去权值最大的边的边权。

合并后的区间最左最右竖边权值、横边权值分别取左区间最左、右区间最右的权值即可。

但是有一个问题，如果左区间（或右区间）只有一条竖边，但是刚好要去掉这条边，那么并后的段所维护的信息就会出现问题，需要特判一下，将最左（或最右）竖边权值、横边权值改到右区间（或左区间）。

为了以上的特判，我们还需要统计区间中的竖边数量，不能直接比较边权，不然会 90 分 WA 掉。（别问我怎么知道的）

因此，区间自然可以用线段树维护，查询、更新时重新合并区间即可。

做法

程序流程

  1. 输入 n 和 m；
  2. 读入边权；
  3. 建树；
  4. 处理询问。

（这不是都是废话吗）

细节

在写 pushup 时要注意以下问题：

  1. pushup 不止要用于合并线段树上节点，还好用于查询时合并答案，所以当前节点、左区间节点、右区间节点要分别传入；
  2. 一定要注意左区间右区间是否对应写对（这个调了好久（悲）；
  3. 注意要在 query 时或者 pushup 函数中新建节点，否则你就会得到一堆 0。

部分代码

线段定义

struct node{
    int l,r,ls,rs; // 左端点，右端点，左区间，右区间

  //                     最左边竖线权值  区间答案
  //                           |            |
    long long hormal,hormar,malver,marver,sum,cntver;
  //            |      |             |          |
  //最左边竖线左边横线最大权值 最右边竖线权值  |
  //                 |                        |
  //     最右边竖线右边横线最大权值     区间内竖边数

}nodes[1500000];

pushup 函数

void pu(int& cur,int ls,int rs){
    if(!ls){ //处理query中未处理完的左右区间未查询为空，如果query已经处理完了就不需要写了
        cur=rs;
        return;
    }
    if(!rs){
        cur=ls;
        return;
    }
    long long mid=nodes[ls].r;
    if(nodes[rs].l!=mid+1) return; // 防炸
    if(!cur){ // 为query新分配一个线段
        cur=alloc++;
        nodes[cur].l=nodes[ls].l;
        nodes[cur].r=nodes[rs].r;
    }
    long long horma = max(max(nodes[ls].hormar,nodes[rs].hormal),max(horup[mid+1],hordn[mid+1])); // 环内横向边最大值
    nodes[cur].cntver=nodes[ls].cntver+nodes[rs].cntver;
    nodes[cur].hormar=nodes[rs].hormar;
    nodes[cur].hormal=nodes[ls].hormal;
    long long vlmar = nodes[ls].marver; //左区间最右的竖边
    long long vrmal = nodes[rs].malver; //右区间最左的竖边
    nodes[cur].sum=nodes[ls].sum+nodes[rs].sum+horup[mid+1]+hordn[mid+1];
    nodes[cur].malver=nodes[ls].malver;
    nodes[cur].marver=nodes[rs].marver;
    if(vlmar>horma&&vlmar>vrmal){ // 左区间提供的竖边最大
        nodes[cur].sum-=vlmar;
        nodes[cur].cntver--;
        if(nodes[ls].cntver==1){
            nodes[cur].malver=vrmal;
            nodes[cur].hormal=max(nodes[cur].hormal,horma);
        }
    }else if(vrmal>horma){ // 右区间提供的竖边最大
        nodes[cur].sum-=vrmal;
        nodes[cur].cntver--;
        if(nodes[rs].cntver==1){
            nodes[cur].marver=vlmar;
            nodes[cur].hormar=max(nodes[cur].hormar,horma);
        }
    }else{
        nodes[cur].sum-=horma;
    }
}

注：本题解参考了第一篇题解的思路，加入了较多个人理解；图片待补充。