[BalticOI 2021 Day2] The short shank题解

· · 题解

题意：

若干间牢房，其中一些会在 t_i 暴乱，每过一时刻所有暴乱的人会使右边的下一个人暴乱（如果没暴乱的话）。可以在至多 D 个人右边放挡板，使其无法传染给下一个人。求 T 时刻最少有多少人暴乱。

显然对于 t_i>T 的 i ，是不会自己暴乱的，只会由其左边的人影响过来（称为 “传染” ）。我们把这些人称作 “普通点” 。反之，会自己暴乱的点称为 “特殊点” 。

同时显然的还有：对于一段连续的普通点，最多只会在其左端点的左侧放置隔板；对于一段连续的特殊点，最多只会在其右端点的右测放置隔板。

然后我们会想到两种统计贡献的方式：对特殊点统计和对普通点统计。 但在研究一番后，发现没有有效的对关键点统计的方法。主要是因为只能设计 dp 维护，但它的状态数是 O(ND) 的。

于是我们对普通点进行统计，令 l_i 表示第一个能传染到他的关键点，那么一个点不会被传染 当且仅当没有 l_i 或 [l_i,i] 中有隔板 。

但如果这样进行 dp ，状态数还是 O(ND) 的，怎么办呢？我们发现对于两个普通点 i<j ，必然有 l_j\leq l_i<i<j 或 l_i<i<l_j<j ，既 只有包含或相离，没有相交 。

证明：即证不存在 l_i<l_j<i<j ，此时有 l_j+(T-t_{l_j})\geq j>i ，所以 l_i 应该是更大的 l_j ，矛盾。

对于每个普通点，把满足 l_j\leq l_i<i<j 的最小普通点 j （如果有的话）认作父亲，然后就会建出一个森林。对于森林中的每个叶节点，满足 l_i=i-1 ，在 l_i 和 i 之间放一个隔板，会且只会让树上从 i 到根的所有结点不会暴乱。同时，对于任意一种有贡献的放隔板法，必然能找到板子后面第一个 i 使得它到根节点路径上的节点不会暴乱。

因此在树上选 D 条从叶节点向上的不交的链，使其点集交最大即可。可以 长链剖分 后，选前 D 长链。

证明：首先对于一个最优解，每一条链都会让最上端点尽量往上。那么对于一种可能的最优解：

图丑勿怪

讨论某一点的子树，对于一条过根却不是最长链的链（A），如果最长链剩下部分有边，不妨（？）假设剩下部分只有一条链（B），且其包含了最长链剩下部分所有的点，那么将 A 下半部与 B 交换，答案不变；如果最长链剩下部分无边，将 A 直接变成最长链，答案也不降。

对于 “不妨”，可以先向下讨论最长链下方子树，就能得到最长链内只有一条链的结论。

建树时可以顺序依次枚举，将还能施加影响的特殊点及 l_i 是该点的最大的 i 在栈中维护，每次清掉栈顶不可能传染到他的特殊点（肯定也影响不到后面），在清掉的点和第一个能传染到他的点中选深度最大的作为长链并且标上标记（在另一个点的长链中），然后顶掉栈顶的 i 。

把没有 l_i 的点直接加入答案，最后把所有未标记的链扔到优先队列选前 D 长即可。

Code：

#include<cstdio>
#include<queue>
#define max(a,b) (a>b?a:b)
using namespace std;
int n,d,t,a[2000001],ans;
int h[2000001],hp[2000001];
int st[2000001],v[2000001],num;
bool vis[2000001];
int main()
{
    scanf("%d%d%d",&n,&d,&t);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if(a[i]<=t)
        {
            st[++num]=i;
            v[num]=i;
        }
        else
        {
            while(num&&st[num]+t-a[st[num]]<i)
            {
                if(h[v[num]]>h[i])
                {
                    h[i]=h[v[num]]；
                    hp[i]=v[num];
                }
                --num;
            }
            if(num)
            {
                if(h[v[num]]>h[i])
                {
                    h[i]=h[v[num]]；
                    hp[i]=v[num];
                }
                ++h[i];
                vis[hp[i]]=1;
                v[num]=i;
            }
            else ++ans,vis[i]=1;
        }
    }
    priority_queue<int>q;
    for(int i=n;i;--i)
        if(!vis[i])
            q.push(h[i]);
    while(d--)
    {
        if(q.empty())break;
        ans+=q.top();q.pop();
    }
    printf("%d",n-ans);
}