题解：P11518 [CCO 2024] Heavy Light Decomposition

· · 题解

[CCO 2024] Heavy Light Decomposition 题解

博客园链接：[CCO 2024] Heavy Light Decomposition 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

DP，线段树优化。

分析

考虑 a_i,a_{i+1} 间限制：

  2. 考虑使 $a_i$ 为重的两侧最近节点，设为 $l,r$。特别地，若左侧不存在，则 $l=0$；若右侧不存在，则 $r=n+1$。同理，$a_{i+1}$ 的设为 $L,R$。 由于将序偶 $<l,r>$ 和 $<L,R>$ 对换后几乎等价，不妨假设有 $R<r$ 以减少情况数。那么只有两种情况： 1. $l\le L$： 此时只有 $a_{i+1}$ 可以为重，区间范围是 $<(l,i],[i+1,r)>\setminus<(L,i],[i+1,R)>$，放到一个二维平面上就是一个 $(l,i]\times[i+1,r)$ 的矩形减去 $(L,i]\times [i+1,R)$ 的矩形。 2. $l>L$： 那么 $a_i,a_{i+1}$ 都可能为重。 - $a_i$ 为重，区间范围为 $<(L,l],[i+1,R)>$。 - $a_{i+1}$ 为重，区间范围为 $<(l,i],[R,r)>$。

除相邻点限制之外，还有交替的限制，那么我们将上面的矩形加减放到两个数组 sum_{0/1} 中实现，sum_{0/1} 分别表示 i 为奇数的点要为轻、为重。发现，如果满足 sum_{0/1,j,i}=i-j(j\le i)，则 [i,j] 是一个合法的”好数组“，可以得到一个二维前缀和的 O(n^2) 算法。

设 f_i 为前 i 个数的合法方案数，那么有：

f_0 = 1 \\ f_i = \sum_{j=1}^i f_{j-1} [sum_{0/1,j,i}=i-j] \\

又发现，除 j=i 外，其余 sum_{0,j,i},sum_{1,j,i} 中只有一者可以满足 i-j，且 sum_{0/1,j,i}\le i-j 永远成立，移项，得到 sum_{0/1,j,i}+j\le i。

那么考虑开两棵线段树做扫描线，维护 sum_{0/1,j,i}+j 的最大值以及其对应位置的 DP 值 f_{j-1}，最后查询 f_i 时再减掉 f_{i-1} 即可。

代码

已删去模运算和快读快写。

int n,cha;
int a[N],f[N],pre[N],nxt[N],lst[N];
struct Change {
    bool t;
    int y,xa,xb,v;
    friend bool operator <(Change a,Change b) { return a.y<b.y; }
} Cha[N<<2];
struct Data {
    int mx,val;
    Data(int mx=0,int val=0):mx(mx),val(val) {}

    friend Data operator +(Data A,Data B) {
        Data C(max(A.mx,B.mx),0);
        if(C.mx==A.mx)toadd(C.val,A.val);
        if(C.mx==B.mx)toadd(C.val,B.val);
        return C;
    }
};
struct SEG {
    struct node {
        int tag;
        Data dat;
        node(int tag=0,Data dat=Data()):tag(tag),dat(dat) {}

        void down(int _tag) { dat.mx+=_tag,tag+=_tag; }
    } tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
    void Up(int p) { tr[p].dat=tr[ls].dat+tr[rs].dat; }

    void Down(int p) { if(tr[p].tag)tr[ls].down(tr[p].tag),tr[rs].down(tr[p].tag),tr[p].tag=0; }

    void Build(int p=1,int l=1,int r=n) {
        tr[p]=node();
        if(l==r)return;
        Build(ls,l,mid),Build(rs,mid+1,r),Up(p);
    }

    void Plus(int L,int R,int d,int p=1,int l=1,int r=n) {
        if(L<=l&&r<=R)return tr[p].down(d);
        Down(p);
        if(L<=mid)Plus(L,R,d,ls,l,mid);
        if(mid<R)Plus(L,R,d,rs,mid+1,r);
        Up(p);
    }

    void Change(int x,int d,int p=1,int l=1,int r=n) {
        if(l==r)return tr[p].dat=Data(l,d),void();
        return Down(p),x<=mid?Change(x,d,ls,l,mid):Change(x,d,rs,mid+1,r),Up(p);
    }
#undef ls
#undef rs
#undef mid
} seg[2];

void Plus(bool t,int xa,int xb,int ya,int yb,int d) {
    if(xa<=xb&&ya<=yb)Cha[++cha]=Change{t,ya,xa,xb,d},Cha[++cha]=Change{t,yb+1,xa,xb,-d};
}

void Plus(int i) {
    if(a[i]==a[i+1])return;
    bool t(i&1);
    int l(pre[i]),r(nxt[i]),L(pre[i+1]),R(nxt[i+1]);
    if(l<1&&L<1&&r>n&&R>n)return;
    if(R>r)swap(l,L),swap(r,R),t=!t;
    if(l<=L)Plus(t,l+1,i,i+1,r-1,1),Plus(t,L+1,i,i+1,R-1,-1);
    else Plus(!t,L+1,l,i+1,R-1,1),Plus(t,l+1,i,R,r-1,1);
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    /*DE("Input & Init");*/
    I(n);
    FOR(i,1,n)I(a[i]),pre[i]=lst[a[i]],nxt[lst[a[i]]]=i,lst[a[i]]=i;
    FOR(i,1,n)if(lst[i])nxt[lst[i]]=n+1;
    /*DE("Init");*/
    seg[0].Build(),seg[0].Change(1,f[0]=1),seg[1].Build(),seg[1].Change(1,f[0]=1);
    FOR(i,1,n-1)Plus(i);
    sort(Cha+1,Cha+cha+1);
    /*DE("Solve");*/
    int it(1);
    FOR(i,1,n) {
        while(it<=cha&&Cha[it].y<=i)seg[Cha[it].t].Plus(Cha[it].xa,Cha[it].xb,Cha[it].v),++it;
        if(seg[0].tr[1].dat.mx==i)toadd(f[i],seg[0].tr[1].dat.val);
        if(seg[1].tr[1].dat.mx==i)toadd(f[i],seg[1].tr[1].dat.val);
        toadd(f[i],Mod-f[i-1]);
        if(i<n)seg[0].Change(i+1,f[i]),seg[1].Change(i+1,f[i]);
    }
    /*DE("Output");*/
    O(f[n],'\n');
    return 0;
}