[Luogu]P4344 脑洞治疗仪
本文最后更新于 213 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/lp4344/

题意

题目传送门

需要实现以下区间操作:

  1. 将区间 $[l,r]$ 赋值为0
  2. 将 $[l_0,r_0]$ 的和分配给 $[l_1,r_1]$
  3. 询问 $[l,r]$ 区间内连续 $0$ 区间的最长长度

思路

一道数据结构题,涉及大量区间操作,可以想到用线段树解决。

区间维护

用线段树维护最长连续区间是老套路了。

维护如下值:

  1. lmax: 从左端点开始连续 $0$ 区间的长度
  2. rmax: 从右端点开始连续 $0$ 区间的长度
  3. mmax: 整个区间中最长连续 $0$ 区间的长度
  4. sum: 区间和,用于判断区间中0/1个数

转移时:

  1. lmax: 左区间的 lmax,如果左区间全为 $0$ 则加上右区间的 lmax
  2. rmax: 右区间的 rmax,如果右区间全为 $0$ 则加上左区间的 rmax
  3. mmax: 不跨越左右区间的最大值与跨越左右区间的最大值
  4. sum: 左右区间和的和

实现代码:

inline void pushup(node &now,node &ls,node &rs)
{
    now.sum = ls.sum + rs.sum;
    now.lmax = ls.lmax;
    if(ls.sum == 0) now.lmax += rs.lmax;
    now.rmax = rs.rmax;
    if(rs.sum == 0) now.rmax += ls.rmax;
    now.mmax = max(ls.mmax,rs.mmax,ls.rmax + rs.lmax);
}

区间操作

题目中有三种操作:

  1. 将区间 $[l,r]$ 赋值为0
  2. 将 $[l_0,r_0]$ 的和分配给 $[l_1,r_1]$
  3. 询问 $[l,r]$ 区间内连续 $0$ 区间的最长长度

那么需要实现的操作有:

  1. 区间赋值
  2. 区间和查询
  3. 最长连续 $0$ 区间长度查询
  4. 区间修复,即已知可用 $1$ 的个数,从左到右分配给 $0$

其中区间赋值和区间和不再赘述。

维护区间赋值 tag,$1$ 代表赋值为 $1$,$-1$ 代表赋值为 $0$,$0$ 代表无标记。

最长连续 $0$ 区间长度

类似区间和查询,合并左右区间答案时与 pushup 操作类似,可以复用 pushup 函数。

node askmax(const int &p, const int &ll, const int &rr)
{
    node &now = A[p], &ls = A[p << 1], &rs = A[p << 1 | 1];
    if (now.l >= ll && now.r <= rr) return now;
    pushdown(p);
    if (ll <= ls.r && rr >= rs.l) 
    {
        node lres = askmax(p << 1, ll, rr);
        node rres = askmax(p << 1 | 1, ll, rr);
        node res;
        pushup(res, lres, rres);
        return res;
    }
    else if (rr <= ls.r) return askmax(p << 1, ll, rr);
    else return askmax(p << 1 | 1, ll, rr);
}

区间修复

区间修复是本题的特色操作,可以分为两步来解决:

  1. 询问 $[l_0,r_0]$ 区间和,记为 canuse,将 $[l_0,r_0]$ 赋值为 $0$
  2. 可用 canuse 个 $1$,填补区间 $[l_1,r_1]$

将区间填补看做区间赋值为 $1$,赋值条件为可用 $1$ 个数大于等于区间 $0$ 个数。

区间中 $0$ 的个数可以用区间长度减去区间和算出。

若可用的 $1$ 个数大于当前区间 $0$ 的个数,则进行区间赋值。

if(canuse >= now.len - now.sum)
{
    canuse -= now.len - now.sum;
    now.lmax = now.rmax = now.mmax = 0;
    now.sum = now.len;
    now.tag = 1;
    return;
}

如果不够的话,向下递归。

先处理左半边,再处理右半边,即可实现从左到右填补。

Code

维护值较多的线段树,笔者习惯使用结构体。

时间复杂度 $O(n \log n)$。

#include <cstdio>
template <typename T>
inline T min(const T &a, const T &b) { return a < b ? a : b; }
template <typename T>
inline T max(const T &a, const T &b) { return a > b ? a : b; }
template <typename T>
inline T max(const T &a, const T &b, const T &c) { return max(c, max(a, b)); }
template <typename T>
void read(T &r)
{
    static char c;
    r = 0;
    for (c = getchar(); c > '9' || c < '0'; c = getchar());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
}
const int maxn = 2e5 + 100;
int n, m;
struct node
{
    int l, r, lmax, rmax, mmax, tag, sum, len;
} A[maxn << 2];
inline void pushup(node &now, node &ls, node &rs)
{
    now.sum = ls.sum + rs.sum;
    now.lmax = ls.lmax + !ls.sum * rs.lmax;              //sum==0时全覆盖
    now.rmax = rs.rmax + !rs.sum * ls.rmax;              //全覆盖则加上另一边
    now.mmax = max(ls.mmax, rs.mmax, ls.rmax + rs.lmax); //取左半边最长、右半边最长或跨越中界最长
}
inline void pushdown(const int &p)
{
    node &now = A[p], &ls = A[p << 1], &rs = A[p << 1 | 1];
    if (now.tag == 0) return;
    if (now.tag == 1) //tag==1表示全修补
    {
        ls.lmax = ls.rmax = ls.mmax = 0;
        rs.lmax = rs.rmax = rs.mmax = 0;
        ls.sum = ls.len;
        rs.sum = rs.len;
    }
    else if (now.tag == -1) //tag==-1表示全挖空
    {
        ls.lmax = ls.rmax = ls.mmax = ls.len;
        rs.lmax = rs.rmax = rs.mmax = rs.len;
        ls.sum = 0;
        rs.sum = 0;
    }
    ls.tag = rs.tag = now.tag; //区间覆盖标记下传
    now.tag = 0;
}
void build(const int &l, const int &r, const int &p)
{
    A[p].l = l, A[p].r = r, A[p].sum = A[p].len = r - l + 1; //初始全1
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}
void clean(const int &p, const int &ll, const int &rr)
{
    node &now = A[p], &ls = A[p << 1], &rs = A[p << 1 | 1];
    if (now.l >= ll && now.r <= rr)
    {
        now.lmax = now.rmax = now.mmax = now.len;
        now.sum = 0;
        now.tag = -1;
        return;
    }
    pushdown(p);
    if (ll <= ls.r) clean(p << 1, ll, rr);
    if (rr >= rs.l) clean(p << 1 | 1, ll, rr);
    pushup(now, ls, rs);
}
int asksum(const int &p, const int &ll, const int &rr)
{
    node &now = A[p], &ls = A[p << 1], &rs = A[p << 1 | 1];
    if (now.l >= ll && now.r <= rr) return now.sum;
    pushdown(p);
    int res = 0;
    if (ll <= ls.r) res = asksum(p << 1, ll, rr);
    if (rr >= rs.l) res += asksum(p << 1 | 1, ll, rr);
    return res;
}
//返回值代表使用了多少
int canuse;
void repair(const int &p, const int &ll, const int &rr) //val代表还能填多少个1
{
    if (canuse <= 0) return; //剩余额度<=0则直接返回
    node &now = A[p], &ls = A[p << 1], &rs = A[p << 1 | 1];
    if (now.l >= ll && now.r <= rr)
    {
        if (canuse >= now.len - now.sum) //足够填满当前区间
        {
            canuse -= now.len - now.sum;
            now.lmax = now.rmax = now.mmax = 0;
            now.sum = now.len;
            now.tag = 1;
            return;
        }
        pushdown(p);
        repair(p << 1, ll, rr), repair(p << 1 | 1, ll, rr);
        pushup(now, ls, rs);
        return;
    }
    pushdown(p);
    if (ll <= ls.r) repair(p << 1, ll, rr);
    if (rr >= rs.l) repair(p << 1 | 1, ll, rr);
    pushup(now, ls, rs);
}
node askmax(const int &p, const int &ll, const int &rr) //询问最长连续0区间
{
    node &now = A[p], &ls = A[p << 1], &rs = A[p << 1 | 1];
    if (now.l >= ll && now.r <= rr) return now;
    pushdown(p);
    if (ll <= ls.r && rr >= rs.l) //询问区间两边都有,跨越中点
    {
        node lres = askmax(p << 1, ll, rr), rres = askmax(p << 1 | 1, ll, rr), res;
        pushup(res, lres, rres); //询问得到左半边、右半边答案,按左右区间方法上推
        return res;
    }
    else if (rr <= ls.r) return askmax(p << 1, ll, rr); //只在一边,直接向下递归
    else return askmax(p << 1 | 1, ll, rr);
}
int main()
{
    read(n), read(m);
    build(1, n, 1);
    while (m--)
    {
        int opt, l, r, l1, r1;
        read(opt), read(l), read(r);
        if (opt == 0) clean(1, l, r);
        else if (opt == 1)
        {
            read(l1), read(r1);
            canuse = asksum(1, l, r); //先询问得到可用的1的个数
            clean(1, l, r);           //清除区间
            repair(1, l1, r1);        //进行填补
        }
        else if (opt == 2) printf("%d\n", askmax(1, l, r).mmax);
    }
    return 0;
}
本文标题:[Luogu]P4344 脑洞治疗仪
本文作者:Clouder
本文链接: https://www.codein.icu/lp4344/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇