P2418 yyy loves OI IV

Pop_Agoni · 2025-11-09 18:57:03 · 题解

P2418 yyy loves OI IV

前言：

首先想的 DP 是这样的，记 f_i 表示以 i 同学为终点的最少的房间数。

很容易写出转移方程式：

其中 j 需要满足区间 [j,i] 全都只膜拜一个人，或者二者相差小于 m。

正解：

上述时间复杂度为 O(n^2)。

因为没有任何优化。

这个转移方程式十分常见，但是判断是否可以转移的条件略困难。

我们考虑优化。

分情况讨论。

1. 区间 [j,i] 全部膜拜一个人。

那么我们只需要计算出对于当前的同学最前的一个膜拜跟他相同的一个同学，记录为 lst。

那么 i 肯定是从 lst 转移过来的，在满足条件一的情况下。

2. 区间 [j,i] 膜拜的人数相互小于等于 m

发现只有两种的膜拜情况，又加上要时刻保持二者差值小于等于 m。

我们可以考虑到将其转换成类似于括号匹配的问题。

我们记 sum_{i,1} 表示前 i 个人里膜拜第一个人的人数。

我们将下标相同的项放在一起，不同的项放到另一边。

对于上面的这么一个条件实际上就是求一个对于 j 的合法区间。

那么我们将 f_j 存在一颗线段树上，下标为 sum_{i,2}-sum_{i,1}。

查询更新即可。

记得加上一段区间内所有人膜拜的人都一样的情况。

#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1) 
using namespace std;
const int N=5e5+5;
int n,m;
int a[N];
int tr[N<<4],sum[N][3],f[N],t,l,r,pos,lstc;
int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tr[x];
    int mid=(l+r)>>1,mn=1e9;
    if(L<=mid) mn=min(mn,query(ls(x),l,mid,L,R));
    if(R>mid) mn=min(query(rs(x),mid+1,r,L,R),mn);
    return mn;
}
void pushup(int x){tr[x]=min(tr[ls(x)],tr[rs(x)]);}
void build(int x,int l,int r){
    if(l==r){
        tr[x]=n+1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(x),l,mid),build(rs(x),mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int id,int val){
    if(l==r){
        tr[x]=min(tr[x],val);
        return;
    }
    int mid=(l+r)>>1;
    if(id<=mid) update(ls(x),l,mid,id,val);
    else update(rs(x),mid+1,r,id,val);
    pushup(x);
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,-n,n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i][1]=sum[i-1][1]+(a[i]==1);
        sum[i][2]=sum[i-1][2]+(a[i]==2);
    }
    for(int i=1;i<=n;i++) f[i]=n+1;
    f[0]=0;
    update(1,-n,n,0,0);

    for(int i=1;i<=n;i++){
        t=sum[i][1]-sum[i][2];
        l=-m+t,r=m+t;
        l=max(-n,l),r=min(r,n);
        if(lstc!=a[i]) lstc=a[i],pos=i-1;
        f[i]=min(f[pos],query(1,-n,n,l,r))+1;
        // t=sum[i][2]-sum[i][1];
        update(1,-n,n,t,f[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}

upd：“线段树”打成了“线椴树”，已改。