首页 > 其他分享 >题解:P5618 [SDOI2015] 道路修建

题解:P5618 [SDOI2015] 道路修建

时间:2024-09-09 21:03:19浏览次数:11  
标签:ld int 题解 边权 ret lv lu P5618 SDOI2015

题意

给定一个 \(2\times N\) 的网格,网格上的点和上下左右连边。

要求支持以下几种操作:

  • 修改某条边的边权。

  • 求满足 \(y\in[l,r]\) 的点构成的点集的最小生成树。

分析

这道题的想法和 P4246 [SHOI2008] 堵塞的交通 很相似。

注意到 \(N, M \leq 6\times 10^4\),并且查询的是 \(y\in[l,r]\) 的点构成的点集的最小生成树,考虑使用线段树维护。

我们考虑如何合并两个区间。

例如,下图的两个区间:

首先,我们将两个区间之间的边 \(BC, FG\) 加入这两个联通块中,让它们成为一个联通块。

因为 \(B\) 和 \(F\) 是联通的,\(C\) 和 \(G\) 是联通的,这样势必会形成一个环。

如图:

为了让它成为一棵树,我们需要删掉其中的一条边。

并且为了保证它是一棵最小生成树,我们应该删去边权最大的边。

到这里,我们维护的对象就显而易见了。

我们维护以下值:

  • lu:最左侧的垂直的生成树边上端点到左上角这一段中边的边权的最大值(即 \(AE\) 段中的边权最大值)
  • ld:最左侧的垂直的生成树边下端点到左下角这一段中边的边权的最大值(即 \(CG\) 段中的边权最大值)
  • ru:最右侧的垂直的生成树边上端点到右上角这一段中边的边权的最大值(即 \(BF\) 段中的边权最大值)
  • rd:最右侧的垂直的生成树边下端点到右下角这一段中边的边权的最大值(即 \(DH\) 段中的边权最大值)
  • lv:最左侧的垂直的生成树边的边权(即 \(EG\) 的边权)
  • rv:最右侧的垂直的生成树边的边权(即 \(FH\) 的边权)
  • ans:该段的最小生成树的边权和。

我们再回头看我们要合并的东西:

我们要删除的就是 \(IK,KF,FG,LG,JL,CJ,BC,IB\) 这些段中边权最小的一条边。

发现如果删除的是 \(KF,FG,LG,CJ,BC,IB\) 这些非垂直边,合并出的新段直接继承左右两端的信息即可。

但是如果删去了垂直边,可能出现某一侧区间没有垂直边的情况。

所以我们需要记录一个 cnt 来表示某个区间中有多少条垂直边。

假设左侧失去了垂直边,那么新区间的 lv 就应该是右区间的 lv,其他的信息同理。

Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 60004

/*
lu           ru  vu
-+-+-+-+-+-+--- ==== ---+-+-+
   |       |            |  
  lv       rv           |  
   |       |            |  
-+-+-+-+-+-+--- ==== ---+-+-+
ld           rd  vd
*/

int vu[maxn], vd[maxn];

struct SegT
{
    struct node
    {
        int R, lv, rv, lu, ru, ld, rd, cnt, ans;
        node(int p=0, int v=0) {R=p, lv=rv=ans=v, lu=ru=ld=rd=0, cnt=1;}
        friend node operator+(node a, node b)
        {
            node ret;
            ret.R=b.R;
            ret.ans=a.ans+b.ans+vu[a.R]+vd[a.R];
            ret.cnt=a.cnt+b.cnt;
            int mx=max({vu[a.R], vd[a.R], a.ru, a.rd, b.lu, b.ld, a.rv, b.lv});
            ret.ans-=mx;
            ret.lv=a.lv, ret.rv=b.rv;
            ret.lu=a.lu, ret.ld=a.ld;
            ret.ru=b.ru, ret.rd=b.rd;
            if(mx==a.rv)
            {
                ret.cnt--;
                if(a.cnt==1)
                {
                    ret.lv=b.lv, ret.rv=b.rv;
                    ret.ld=max({a.ld, a.rd, b.ld, vd[a.R]});
                    ret.lu=max({a.lu, a.ru, b.lu, vu[a.R]});
                    ret.ru=b.ru, ret.rd=b.rd;
                }
            }
            else if(mx==b.lv)
            {
                ret.cnt--;
                if(b.cnt==1)
                {
                    ret.lv=a.lv, ret.rv=a.rv;
                    ret.rd=max({b.rd, b.ld, a.rd, vd[a.R]});
                    ret.ru=max({b.ru, b.lu, a.ru, vu[a.R]});
                    ret.lu=a.lu, ret.ld=a.ld;
                }
            }
            return ret;
        }
    }tr[maxn<<2];

    #define lc x<<1
    #define rc x<<1|1
    #define mid ((l+r)>>1)
    #define lson lc, l, mid
    #define rson rc, mid+1, r

    void modify(int x, int l, int r, int p, int v)
    {
        if(l==r) return tr[x]=node(p, v), void();
        if(p<=mid) modify(lson, p, v);
        if(p>mid)  modify(rson, p, v);
        tr[x]=tr[lc]+tr[rc];
    }

    void upd(int x, int l, int r, int p)
    {
        if(l==r) return;
        if(p<=mid) upd(lson, p);
        if(p>mid)  upd(rson, p);
        tr[x]=tr[lc]+tr[rc];
    }

    auto query(int x, int l, int r, int L, int R)
    {
        if(L<=l&&r<=R) return tr[x];
        if(R<=mid) return query(lson, L, R);
        if(L>mid)  return query(rson, L, R);
        return query(lson, L, R)+query(rson, L, R);
    }
}tr;

int main()
{
    int n, m;
    cin>>n>>m;
    for(int i=1;i<n;i++) cin>>vu[i];
    for(int i=1;i<n;i++) cin>>vd[i];
    for(int i=1, t;i<=n;i++)
    {
        cin>>t;
        tr.modify(1, 1, n, i, t);
    }
    char op;
    int x0, y0, x1, y1, w, L, R;
    while(m--)
    {
        cin>>op;
        if(op=='C')
        {
            cin>>x0>>y0>>x1>>y1>>w;
            if(x0==x1) (x0==1?vu:vd)[min(y0, y1)]=w, tr.upd(1, 1, n, min(y0, y1));
            else tr.modify(1, 1, n, y0, w);
        }
        if(op=='Q')
        {
            cin>>L>>R;
            cout<<tr.query(1, 1, n, L, R).ans<<'\n';
        }
    }
}

标签:ld,int,题解,边权,ret,lv,lu,P5618,SDOI2015
From: https://www.cnblogs.com/redacted-area/p/18405330

相关文章

  • 题解:P6089 [JSOI2015] 非诚勿扰
    分析首先我们要求出对于第\(i\)位女性,她选择每个列表中的男性的概率是多少。第一轮选择第一位的概率为\(p\),选择第二位的概率为\(p(1-p)\),以此类推。显然第一轮选择第\(k\)位的概率为\(p(1-p)^{k-1}\)。假设列表中有\(n\)名男性,那么第二轮选择第一位的概率为\(p(1-p......
  • 题解:P3968 [TJOI2014] 电源插排
    题意维护一个\(01\)串,初始均为\(0\),支持:单点将\(1\)修改为\(0\)。查询区间中\(1\)的个数。查询最长且最靠右的连续\(0\)段的靠右的中点,并将其改为\(1\)。分析第一个操作和第二个操作显然使用动态开点线段树维护。我们只需要解决第三个操作。我们用平衡树存储......
  • CF1621G Weighted Increasing Subsequences 题解
    题目链接点击打开链接题目解法这种题就感觉每一步都不难想,但串在一起就不会显然考虑位置\(x\)作为\(lis\)的一部分,合法的\(lis\)的个数合法的约束是:令\(lis\)的最后一个位置为\(last\),满足\(\max\{a_{last+1},...,a_n\}>a_x\)不难发现,合法的\(last\)是一段区间......
  • 【最新华为OD机试E卷-支持在线评测】通过软盘拷贝文件(200分)多语言题解-(Python/C/Ja
    ......
  • P7230 题解
    P7230思路对每个左端点维护右端点\(res_i\)。操作形如删去一个数再加入一个数。如果删掉\(p\)上的\(a_p\),找到左右最近的\(l,r\)使得\(a_l=a_r=a_p\)。那么\(res_{l+1},\dotsb,res_p\)对\(r\)取max。实际上要维护\(\maxres_i-i+1\),因为\(res_i\)单调,所以相当于......
  • 【题解】Solution Set - NOIP2024集训Day25 概率期望 dp
    【题解】SolutionSet-NOIP2024集训Day25概率期望dphttps://www.becoder.com.cn/contest/5515「QOJ2606」Gachapon\(f_{i,j}\):用一次合法的level-irolling能够抽到的\(j\)的期望个数。\(h_{i,j,k}\):在\(i\)次操作之内,抽到恰好\(k\)个\(j\)的概率。\[h_{i,j,k......
  • luogu4198题解
    随机说话这个题做法没见过记一下。我一开始以为是李超树的题,结果把李超树打上之后就不会做了。然后题读错了写了一个弱化版。题目分析做法参考这个题题意只是假装是一个有关线段的题。简化之后的题意如下。有一个初始都为\(0\)的实数数列,每一次会修改位置\(x\)的数为......
  • Flutter 3.24 构建 release 抛出部分依赖 AAPT: error: resource android:attr/lStar
    问题截图:一些讨论:https://github.com/transistorsoft/flutter_background_fetch/issues/369问题原因及解决方案:@Aziz-T该问题与插件的compileSdkVersion和targetSdkVersion有关。出现该问题的原因是部分插件的compileSdkVersion和targetSdkVersion版本过旧。请前往......
  • P2471 [SCOI2007] 降雨量 题解
    题目传送门分析分讨题。首先发现是RMQ问题(区间最值),可以用线段树或ST表来维护(代码为线段树,因为我忘记ST表怎么写了)。然后发现有些年份不明确导致区间判断似乎不好搞。但事实上只要判断下标差是否等于年份差即可得出该区间有无不明确年份。其次考虑“必真”,“必假”,“......
  • 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)
    约瑟夫问题题目描述个人围成一圈,从第一个人开始报数,数到的人出列,再由下一个人重新从开始报数,数到的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友,而该题是全部出圈。输入......