专栏文章

题解：P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi

RRelibery
P14598题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min1elal
此快照首次捕获于
2025/12/01 18:59
3 个月前
此快照最后确认于
2025/12/01 18:59
3 个月前
查看原文

思路

注意到这是一个区间查询问题，只需要解决怎么把小区间合并到大区间，就可以用线段树求解。
如何合并？
我们维护区间的四个状态：以红色为底的堆的数量 rfrf，以蓝色为底的堆的数量 bfbf，以红色为顶的堆的数量 rtrt，以蓝色为顶的堆的数量 btbt。我们把每个区间都看作这些堆的集合，顶（或底）的数量之和就是区间最少堆的个数。
不难发现，由于区间在 ll 到 rr 递增，要用小区间合并出一个大区间，我们将左区间以红色为底的堆放在右区间以蓝色为顶的堆上，左区间以蓝色为底的堆放在右区间以红色为顶的堆上，这样一定是放的上去的，且可以证明一定是最优的。

合并代码

CPP
void pushup(ll x)
{
    c[x].rt=c[2*x].rt+max(0,c[2*x+1].rt-c[2*x].bf);
    c[x].bt=c[2*x].bt+max(0,c[2*x+1].bt-c[2*x].rf);
    c[x].rf=c[2*x+1].rf+max(0,c[2*x].rf-c[2*x+1].bt);
    c[x].bf=c[2*x+1].bf+max(0,c[2*x].bf-c[2*x+1].rt);
    return;
}

初始化

很简单，对于每一个长度为 11 的区间，其以对应颜色为底和顶的数量都为 11，另外一种颜色则都为 00。

总结

一道较为简单的线段树题目，只要想出了区间合并的方式，就得以解决，甚至不需要修改。
时间复杂度 O(nlog⁡q)O(n\log{q})。

参考代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+10;
struct tower{
    int rt,bt,rf,bf;
}c[4*MAXN],tmp;
ll n,q;
string s;
void pushup(ll x)
{
    c[x].rt=c[2*x].rt+max(0,c[2*x+1].rt-c[2*x].bf);
    c[x].bt=c[2*x].bt+max(0,c[2*x+1].bt-c[2*x].rf);
    c[x].rf=c[2*x+1].rf+max(0,c[2*x].rf-c[2*x+1].bt);
    c[x].bf=c[2*x+1].bf+max(0,c[2*x].bf-c[2*x+1].rt);
    return;
}
void build(ll lf,ll rt,ll x)
{
    if(lf==rt)
    {
        if(s[lf-1]=='C')
        {
            c[x].rf=1;
            c[x].rt=1;
        }
        else{
            c[x].bf=1;
            c[x].bt=1;
        }
        return;
    }
    ll mid=(lf+rt)/2;
    build(lf,mid,2*x);build(mid+1,rt,2*x+1);pushup(x);return;
}
bool rgin(int ql,int qr,int lf,int rt)
{
	if(ql<=lf&&qr>=rt) return 1;
	return 0;
}
bool rgout(int ql,int qr,int lf,int rt)
{
	if(lf>qr||rt<ql) return 1;
	return 0;
}
tower check(ll ql,ll qr,ll lf,ll rt,ll x)
{
    tower ans={0,0,0,0},ans1={0,0,0,0},ans2={0,0,0,0};
    if(rgout(ql,qr,lf,rt))
        return ans;
    if(rgin(ql,qr,lf,rt))
        return c[x];
    ll mid=(lf+rt)/2;
    ans1=check(ql,qr,lf,mid,2*x);ans2=check(ql,qr,mid+1,rt,2*x+1);
    ans.rt=ans1.rt+max(0,ans2.rt-ans1.bf);
    ans.bt=ans1.bt+max(0,ans2.bt-ans1.rf);
    ans.rf=ans2.rf+max(0,ans1.rf-ans2.bt);
    ans.bf=ans2.bf+max(0,ans1.bf-ans2.rt);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>s;
    ll u,v;
    build(1,n,1);
    for(int i=1;i<=q;i++)
    {
        cin>>u>>v;
        tmp=check(u,v,1,n,1);
        cout<<tmp.bf+tmp.rf<<"\n";
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...