题解：P15849 三只迅猛龙，八叉线段树

markding · 2026-08-06 22:30:22 · 题解

记 s_1,s_2,s_3 数组分别为每种颜色出现次数的前缀和。

则对于区间 [l+1,r]，颜色 x 出现的次数为 s_{x,r}-s_{x,l}，记为 v_x。

题目中的条件为 \min\{v_1,v_2,v_3\}+k\ge \max\{v_1,v_2,v_3\}。

这即是说，对于任意的两种不同颜色 x,y，都有 k\ge v_y-v_x，由于 x,y 可任意交换，则钦定 x<y 时有 -k\le v_x-v_y\le k。

展开这个东西后是 -k+s_{x,l}-s_{y,l}\le s_{x,r}-s_{y,r}\le k+s_{x,l}-s_{y,l}，且 \forall(x,y)\in\{(1,2),(2,3),(1,3)\} 成立。因此我们可以计算这三种 s_x-s_y 的数组。

为了寻找满足条件的最长连续子区间，我们对于每一个 r，寻找合法的最左的 l。这是一个三维偏序的形式。

好的认真分析完了，下面开始搞笑。

我们考虑建一个动态开点的八叉线段树，修改/询问时将偏序的三个维度进行左右的递归。写法与普通单点修改、区间查询最小值的线段树比较类似，但是需要复制八份并进行边界判断。

时间复杂度应是 O(n\log^3n)。你问这么劣的做法你是咋敢写的？因为它跑得飞快。

代码使用 AI 生成。

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+5,M=5e6+5,INF=0x3f3f3f3f;
int ans,node,n,k,a[N],tr[M],son[M][8],s[N][3],v[N][3];
void change(int& x,int lf,int rf,int lg,int rg,int lh,int rh,int f,int g,int h,int o)
{
    if(lf>rf || lg>rg || lh>rh)return;
    if(!x){tr[x=++node]=INF;}
    if(lf==rf && lg==rg && lh==rh){tr[x]=min(tr[x],o);return;}
    int mf=lf+rf>>1,mg=lg+rg>>1,mh=lh+rh>>1;
    if(f<=mf && g<=mg && h<=mh)change(son[x][0],lf,mf,lg,mg,lh,mh,f,g,h,o);
    if(f<=mf && g<=mg && h>mh)change(son[x][1],lf,mf,lg,mg,mh+1,rh,f,g,h,o);
    if(f<=mf && g>mg && h<=mh)change(son[x][2],lf,mf,mg+1,rg,lh,mh,f,g,h,o);
    if(f<=mf && g>mg && h>mh)change(son[x][3],lf,mf,mg+1,rg,mh+1,rh,f,g,h,o);
    if(f>mf && g<=mg && h<=mh)change(son[x][4],mf+1,rf,lg,mg,lh,mh,f,g,h,o);
    if(f>mf && g<=mg && h>mh)change(son[x][5],mf+1,rf,lg,mg,mh+1,rh,f,g,h,o);
    if(f>mf && g>mg && h<=mh)change(son[x][6],mf+1,rf,mg+1,rg,lh,mh,f,g,h,o);
    if(f>mf && g>mg && h>mh)change(son[x][7],mf+1,rf,mg+1,rg,mh+1,rh,f,g,h,o);
    tr[x]=INF;
    for(int i=0;i<8;i++)
        if(son[x][i])tr[x]=min(tr[x],tr[son[x][i]]);
}
int query(int x,int lf,int rf,int lg,int rg,int lh,int rh,int qlf,int qrf,int qlg,int qrg,int qlh,int qrh)
{
    if(lf>rf || lg>rg || lh>rh || !x)return INF;
    if(qlf<=lf && rf<=qrf && qlg<=lg && rg<=qrg && qlh<=lh && rh<=qrh)
        return tr[x];
    int mf=lf+rf>>1,mg=lg+rg>>1,mh=lh+rh>>1,ret=INF;
    if(qlf<=mf && lf<=qrf && qlg<=mg && lg<=qrg && qlh<=mh && lh<=qrh)
        ret=min(ret,query(son[x][0],lf,mf,lg,mg,lh,mh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=mf && lf<=qrf && qlg<=mg && lg<=qrg && qlh<=rh && mh<qrh)
        ret=min(ret,query(son[x][1],lf,mf,lg,mg,mh+1,rh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=mf && lf<=qrf && qlg<=rg && mg<qrg && qlh<=mh && lh<=qrh)
        ret=min(ret,query(son[x][2],lf,mf,mg+1,rg,lh,mh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=mf && lf<=qrf && qlg<=rg && mg<qrg && qlh<=rh && mh<qrh)
        ret=min(ret,query(son[x][3],lf,mf,mg+1,rg,mh+1,rh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=rf && mf<qrf && qlg<=mg && lg<=qrg && qlh<=mh && lh<=qrh)
        ret=min(ret,query(son[x][4],mf+1,rf,lg,mg,lh,mh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=rf && mf<qrf && qlg<=mg && lg<=qrg && qlh<=rh && mh<qrh)
        ret=min(ret,query(son[x][5],mf+1,rf,lg,mg,mh+1,rh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=rf && mf<qrf && qlg<=rg && mg<qrg && qlh<=mh && lh<=qrh)
        ret=min(ret,query(son[x][6],mf+1,rf,mg+1,rg,lh,mh,qlf,qrf,qlg,qrg,qlh,qrh));
    if(qlf<=rf && mf<qrf && qlg<=rg && mg<qrg && qlh<=rh && mh<qrh)
        ret=min(ret,query(son[x][7],mf+1,rf,mg+1,rg,mh+1,rh,qlf,qrf,qlg,qrg,qlh,qrh));
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],a[i]--,s[i][a[i]]++;
    int rt=0;change(rt,-N,N,-N,N,-N,N,0,0,0,0);
    for(int i=1,v0,v1,v2;i<=n;i++)
    {
        for(int j=0;j<3;j++)s[i][j]+=s[i-1][j];
        v0=s[i][0]-s[i][1],v1=s[i][1]-s[i][2],v2=s[i][0]-s[i][2];
        int qry=query(rt,-N,N,-N,N,-N,N,-k+v0,k+v0,-k+v1,k+v1,-k+v2,k+v2);
        ans=max(ans,i-qry);
        change(rt,-N,N,-N,N,-N,N,v0,v1,v2,i);
    }
    cout<<ans;
}