C37 线段树+二分[SHOI2015] 脑洞治疗仪

huangjunhao LV 8 @ 2025-10-13 20:11:13

前言

不知道为什么要用二分，可能是我太菜了，无法想到那么高深的算法。

正文

默认你已经弄懂题意了，可以发现这是一个在序列上的区间操作问题，于是可以考虑使用线段树。

对于每一个节点，我们维护以下信息：

l、r：区间的左右端点
mx、lmx、rmx：区间最大全为 0 的子区间的长度、左起的最大长度、右起的最大长度
lc、rc：区间的第一个字符和最后一个字符
cnt：区间中 1 的个数
tag0、tag1：懒标记，表示当前区间整体赋值为 0 或 1

对于操作 0，进行简单的区修，将整个区间赋值为 0。

对于操作 1，我们首先查询 $[l_0,r_0]$ 中 1 的个数，存到一个全局变量 tot 中，为后续的修补操作做准备，然后将 $[l_0,r_0]$ 这个区间赋值为 0。

在对 $[l_1,r_1]$ 区间进行修补时，为了满足题目中 “脑洞治疗仪仅会尽量填补位置比较靠前的脑洞” 这个原则，我们在走到一个节点时，要按照先访问左儿子后访问右儿子的顺序进行（其实也就是正常的线段树）。

具体来讲，如果当前全局变量 tot 的值大于等于当前区间（ $[l_1,r_1]$ 的一个子区间）中 0 的个数（即当前区间的长度减去区间中 1 的个数），则将当前区间赋值为 0；否则继续向下递归。当然，如果此时 tot 的值为 0 ，直接返回即可。

对于操作 2，利用 “合并物” 的思路进行简单的区查，输出答案即可。

至此，这道题的思路就讲完了，不过在写代码时还是要注意挺多细节的，特别是 pushup 函数的部分。

我的代码：

#include <bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=2e5+10;
using namespace std;
int n,m,tot;
struct trnode{
	int l,r,mx,lmx,rmx,lc,rc,cnt,tag0,tag1;
} tr[N<<2];
void upd0(trnode &p){
	p.mx=p.r-p.l+1;
	p.lmx=p.rmx=p.mx;
	p.lc=p.rc=0;
	p.cnt=0;
	p.tag0=1,p.tag1=0;
}
void upd1(trnode &p){
	p.mx=p.lmx=p.rmx=0;
	p.lc=p.rc=1;
	p.cnt=p.r-p.l+1;
	p.tag0=0,p.tag1=1;
}
void pushup(trnode &p,trnode l,trnode r){
	p.mx=max({l.mx,r.mx,l.rc==r.lc?l.rmx+r.lmx:0});
	p.lmx=max(l.lmx,l.lmx==l.r-l.l+1&&l.rc==r.lc?l.lmx+r.lmx:0);
	p.rmx=max(r.rmx,r.rmx==r.r-r.l+1&&r.lc==l.rc?r.rmx+l.rmx:0);
	p.lc=l.lc,p.rc=r.rc;
	p.cnt=l.cnt+r.cnt;
}
void pushdown(trnode &p,trnode &l,trnode &r){
	if(p.tag0){
		upd0(l),upd0(r);
		p.tag0=0;
	}
	if(p.tag1){
		upd1(l),upd1(r);
		p.tag1=0;
	}
}
void build(int p,int l,int r){
	tr[p]={l,r,0,0,0,1,1,r-l+1,0,0};
	if(l==r)
		return;
	int mid=(l+r)>>1;
	build(lc(p),l,mid);
	build(rc(p),mid+1,r);
}
void update0(int p,int l,int r){
	if(r<tr[p].l||tr[p].r<l)
		return;
	if(l<=tr[p].l&&tr[p].r<=r){
		upd0(tr[p]);
		return;
	}
	pushdown(tr[p],tr[lc(p)],tr[rc(p)]);
	update0(lc(p),l,r);
	update0(rc(p),l,r);
	pushup(tr[p],tr[lc(p)],tr[rc(p)]);
}
void update1(int p,int l,int r){
	if(!tot||r<tr[p].l||tr[p].r<l)
		return;
	if(l<=tr[p].l&&tr[p].r<=r&&tot>=(tr[p].r-tr[p].l+1)-tr[p].cnt){
		tot-=(tr[p].r-tr[p].l+1)-tr[p].cnt;
		upd1(tr[p]);
		return;
	}
	pushdown(tr[p],tr[lc(p)],tr[rc(p)]);
	update1(lc(p),l,r);
	update1(rc(p),l,r);
	pushup(tr[p],tr[lc(p)],tr[rc(p)]);
}
trnode query0(int p,int l,int r){
	if(l<=tr[p].l&&tr[p].r<=r)
		return  tr[p];
	int mid=(tr[p].l+tr[p].r)>>1;
	pushdown(tr[p],tr[lc(p)],tr[rc(p)]);
	if(r<=mid)
		return query0(lc(p),l,r);
	else if(l>mid)
		return query0(rc(p),l,r);
	else{
		trnode res;
		pushup(res,query0(lc(p),l,r),query0(rc(p),l,r));
		return res;
	}
}
int query1(int p,int l,int r){
	if(r<tr[p].l||tr[p].r<l)
		return 0;
	if(l<=tr[p].l&&tr[p].r<=r)
		return tr[p].cnt;
	pushdown(tr[p],tr[lc(p)],tr[rc(p)]);
	return query1(lc(p),l,r)+query1(rc(p),l,r);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,l,r,ll,rr;
		scanf("%d",&op);
		if(op==0){
			scanf("%d%d",&l,&r);
			update0(1,l,r);
		}else if(op==1){
			scanf("%d%d%d%d",&l,&r,&ll,&rr);
			tot=query1(1,l,r);
			update0(1,l,r);
			update1(1,ll,rr);
		}else{
			scanf("%d%d",&l,&r);
			printf("%d\n",query0(1,l,r).mx);
		}
	}
	return 0;
}

结语

总的来讲，这是一道挺好的线段树练习题，不过鉴于笔者水平不高，可能写的比较复杂，讲解和代码中难免会出现各种小问题，敬请谅解。

huangzheng LV 6 SU @ 2025-10-8 17:10:46

C37 线段树+二分 P4344 [SHOI2015] 脑洞治疗仪

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=2e5+10;
struct trnode
{
    int l,r;
    int sum,lmx,rmx,mx;
    int len,tag;
}tr[N<<2];
//sum:区间1的个数
//lmx:区间左起0的长度
//rmx:区间右起0的长度
// mx:区间0的最长长度
//len:区间的长度
//tag:区间赋值标记,无标记:-1,有标记:0或1

void merge(trnode &t,trnode l,trnode r)//上传
{
    t.sum=l.sum+r.sum;
    t.lmx=l.sum ? l.lmx : l.len+r.lmx;
    t.rmx=r.sum ? r.rmx : r.len+l.rmx;
    t.mx=max(max(l.mx,r.mx),l.rmx+r.lmx);
    t.len=l.len+r.len;//不加这句会错，非tr数组中点（比如query函数的返回值）需要赋值len
}
void pd(int p,int v)//操作区间
{
    trnode &t=tr[p];
    if(v==0)//区间赋值为0
    {
        t.mx=t.lmx=t.rmx=t.len;
        t.sum=0; t.tag=0;
    }
    else    //区间赋值为1
    {
        t.mx=t.lmx=t.rmx=0;
        t.sum=t.len; t.tag=1;
    }
}
void pushdown(int p)//下传
{
    if(tr[p].tag==0) pd(lc(p),0),pd(rc(p),0);
    if(tr[p].tag==1) pd(lc(p),1),pd(rc(p),1);
    tr[p].tag=-1;
}
void bt(int p,int l,int r)
{
    tr[p]={l,r,1,0,0,0,r-l+1,-1};
    if(l==r) return;
    int mid=(l+r)>>1;
    bt(lc(p),l,mid);bt(rc(p),mid+1,r);
    merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
void change(int p,int l,int r,int v)//区修
{
    if(r<tr[p].l || tr[p].r<l) return ;
    if(l<=tr[p].l&&tr[p].r<=r){pd(p,v);return;}
    pushdown(p);
    change(lc(p),l,r,v);change(rc(p),l,r,v);
    merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
int q(int p,int l,int r,int v)//查询v(0|1)的个数
{
    if(r<tr[p].l || tr[p].r<l) return 0;
    if(l<=tr[p].l&&tr[p].r<=r)return v==0?(tr[p].len-tr[p].sum):tr[p].sum;
    pushdown(p);
    return q(lc(p),l,r,v)+q(rc(p),l,r,v);
}
trnode query(int p,int l,int r)//区查
{
    if(r<tr[p].l || tr[p].r<l)return {0,0,0,0,0,0,0,-1};
    if(l<=tr[p].l&&tr[p].r<=r) return tr[p];
    pushdown(p);
    trnode t,t1,t2;
    t1=query(lc(p),l,r);
    t2=query(rc(p),l,r);
    merge(t,t1,t2);
    return t;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    bt(1,1,n);
    for(int i=1,op,l0,r0,l1,r1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&l0,&r0);
        if(op==0) change(1,l0,r0,0);
        else if(op==1)
        {
            scanf("%d%d",&l1,&r1);
            int x=q(1,l0,r0,1);if(x==0) continue; //查询1的个数
            change(1,l0,r0,0); //全部变成0
            int l=l1,r=r1+1;   //二分答案
            while(l+1<r)
            {
                int mid=(l+r)>>1;
                if(q(1,l1,mid,0)<=x)l=mid;
                else                r=mid;
            }
            change(1,l1,l,1); //填上1
        } 
        else if(op==2) printf("%d\n",query(1,l0,r0).mx);
    }
    return 0;
}

十分优雅但无法通过luogu加强数据的ODT：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll l, r;
    mutable ll v;
    bool operator<(const node &b) const
    {
        return l < b.l;
    }
};
set<node> s;
auto split(ll x)
{
    auto it = prev(s.upper_bound({x, -1, -1}));
    auto [l, r, v] = *it;
    if (l == x)
        return it;
    if (r < x)
        return s.end();
    s.erase(it);
    s.insert(node{l, x - 1, v});
    // debug(s);
    return (s.insert(node{x, r, v})).first;
}
void op0(ll l, ll r, ll v)
{
    auto itr = split(r + 1), itl = split(l);
    // debug(s);
    s.erase(itl, itr);
    s.insert(node{l, r, v});
}
void op1(ll l1, ll r1, ll l0, ll r0)
{
    auto it2 = split(r1 + 1), it1 = split(l1);
    ll num = 0;
    for (auto it = it1; it != it2; ++it)
    {
        auto [l, r, v] = *it;
        num += (r - l + 1) * v;
    }
    op0(l1, r1, 0);
    auto itr = split(r0 + 1), itl = split(l0);
    ll rpos = 0;
    for (auto it = itl; it != itr; ++it)
    {
        auto [l, r, v] = *it;
        ll len = r - l + 1;
        if (!v)
        {
            if (num > len)
                rpos = r, num -= len;
            else
            {
                rpos = l + num - 1;
                break;
            }
        }
        else
            rpos = r;
    }
    op0(l0, rpos, 1);
}
ll op2(ll l, ll r)
{
    ll num = 0;
    auto itr = split(r + 1), itl = split(l);
    ll lst = 0;
    for (auto it = itl; it != itr; ++it)
    {
        auto [l, r, v] = *it;
        if (v == 0)
            num = max(num, (lst += r - l + 1));
        else
            lst = 0;
    }
    return num;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    s.insert(node{1, n, 1});
    while (m--)
    {
        int op, l, r, x, y;
        cin >> op;
        if (op == 0)
        {
            cin >> l >> r;
            op0(l, r, 0);
        }
        else if (op == 1)
        {
            cin >> l >> r >> x >> y;
            op1(l, r, x, y);
        }
        else
        {
            cin >> l >> r;
            cout << op2(l, r) << '\n';
        }
    }
    return 0;
}

ID

6257

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

Hydro

2 条题解

前言

正文

结语

信息

状态

开发

支持

关于

2 条题解

前言

正文

结语

C37 线段树+二分[SHOI2015] 脑洞治疗仪

信息

状态

开发

支持

关于

还没有账户？

登录