P8492 [IOI2022] Radio Towers

· · 题解

一个不太一样的做法，想的时候一直以为是 2\log，写的时候发现实际上很容易 1\log。

首先考虑 l=1,r=n 怎么做。

可以发现两两可以匹配等价于任意相邻两个可以匹配。

于是考虑对于每个 i 求出 L_i,R_i 分别表示 i 左右两边第一个 \ge a_i+d 的位置。把它看成数轴上的区间 (L_i,R_i)。一组方案合法当且仅当选出的所有 i 所对应的线段两两不交。

此时有一个非常关键的 observation：这些线段相互之间的关系只有包含和相离。

证明只需反证即可，这里不再赘述。

对于一个线段，如果它包含其它线段，那么选择它肯定不优。称一个线段为“好线段”当且仅当它不包含其它线段。显然我们一定可以选择所有的“好线段”，而这就是我们的最优策略。

此时问题就变为了统计“好线段”的个数。

通过分析可以得到，对于一个 i，(L_i,R_i) 是一条好线段等价于 \forall j\in(L_i,R_i),a_i<a_j。

我们可以对于每个 i 求出左右两边第一个比它小的位置，进一步可以求出最大的 d 使得 (L_i,R_i) 是一个“好线段”，设这个值为 w_i。我们的问题就转化为了求出区间中有多少个 \ge d 的 w_i。直接上主席树即可。

吗？

我们会发现可能会有一个 i，满足 (L_i,R_i) 中存在 <a_i 的值，但是这个值在询问的区间外。这种情况下 i 实际上是可以选的，但是我们会认为它不能选，导致算出的答案偏小。

一种无脑的解决方案是直接上三维数点干掉这个情况，时空复杂度都是 O(n\log ^2n)，不知道能不能过。

可以观察到，左右两个边界处各有至多一个 i 被我们漏掉了，考虑如何找到左边界处的 i，右边界处的可以类似处理。

分析 i 的性质：

上面的三条性质的证明都比较容易，这里不再赘述。

有了这些性质，我们可以直接在 [l,r] 的所有前缀最小值构成的序列上二分找到唯一可能合法的 i，再判断其是否合法即可。

前缀最小值序列可以用可持久化数据结构维护，也可以建成一棵树形结构并把二分改为倍增。

至此，我们在 O((n+m)\log n) 的时间复杂度内解决了这道题。

参考代码：

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define clz __builtin_clz
const int N=100005,M=4000005,up=1e9;
int n,a[N],st[N],w[N],w1[N],w2[N],fa1[17][N],fa2[17][N],mx[17][N];
int cntS,rt[N];struct Seg {int vl,ch[2];}sg[M];
int qMx(int l,int r)
{
    if(l>r) return 0;int t=31-clz(r-l+1);
    return max(mx[t][l],mx[t][r-(1<<t)+1]);
}
void upd(int p,int &p1,int l,int r,int x)
{
    sg[p1=++cntS]=sg[p];++sg[p1].vl;if(l==r) return;
    if(x<=mid) upd(sg[p].ch[0],sg[p1].ch[0],l,mid,x);
    else upd(sg[p].ch[1],sg[p1].ch[1],mid+1,r,x);
}
int qSm(int p,int l,int r,int qL,int qR)
{
    if(!p || qL>qR) return 0;
    if(l>=qL && r<=qR) return sg[p].vl;int res=0;
    if(qL<=mid) res=qSm(sg[p].ch[0],l,mid,qL,qR);
    if(qR>mid) res+=qSm(sg[p].ch[1],mid+1,r,qL,qR);return res;
}
void init(int n1,vector<int> a1)
{
    n=n1;for(int i=1;i<=n;++i) a[i]=mx[0][i]=a1[i-1];
    for(int i=1;i<=n;++i)
    {
        while(st[0] && a[i]<a[st[st[0]]]) --st[0];
        fa1[0][i]=st[0]?st[st[0]]:0;st[++st[0]]=i;
        for(int j=1;j<=16;++j) fa1[j][i]=fa1[j-1][fa1[j-1][i]];
    }st[0]=0;for(int i=0;i<=16;++i) fa2[i][n+1]=n+1;
    for(int i=n;i;--i)
    {
        while(st[0] && a[i]<a[st[st[0]]]) --st[0];
        fa2[0][i]=st[0]?st[st[0]]:n+1;st[++st[0]]=i;
        for(int j=1;j<=16;++j) fa2[j][i]=fa2[j-1][fa2[j-1][i]];
    }
    for(int i=1;i<=16;++i) for(int j=1;j+(1<<i)-1<=n;++j)
        mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
    for(int i=1;i<=n;++i)
    {
        w1[i]=qMx(fa1[0][i]+1,i-1)-a[i];
        w2[i]=qMx(i+1,fa2[0][i]-1)-a[i];w[i]=min(w1[i],w2[i]);
        if(w[i]>0) upd(rt[i-1],rt[i],1,up,w[i]);else rt[i]=rt[i-1];
    }
}
bool chk(int x,int l,int r,int d)
{
    if(x<l || x>r || w[x]>=d) return 0;
    if(w1[x]<d && fa1[0][x]>=l) return 0;
    if(w2[x]<d && fa2[0][x]<=r) return 0;return 1;
}
int max_towers(int l,int r,int d)
{
    int t,t1=++r,t2=++l,res;
    res=qSm(rt[r],1,up,d,up)-qSm(rt[l-1],1,up,d,up);
    for(int i=16;i>=0;--i)
    {t=fa1[i][t1];if(t>=l && qMx(t+1,r)<a[t]+d) t1=t;}
    for(int i=16;i>=0;--i)
    {t=fa2[i][t2];if(t<=r && qMx(l,t-1)<a[t]+d) t2=t;}
    return res+chk(t1,l,r,d)+(t1!=t2 && chk(t2,l,r,d));
}