题目内容

P4198

大意:维护一串序列,单点修改,在线查询 LIS

解题思路

首先这题要注意精度问题,有可能会出现玄学的精度错误

分析题意:考虑看到的楼房最高点 (i,H_i),不难发现能看到的楼房的最高点的斜率都是递增的,即 k_i=i/H_i 满足单调递增(这应该很好想)。发现大区间的信息可以由小区间合并而来,可以使用线段树。这里的单点修改很简单,主要的难点在于如何在 pushup 时合并子区间的信息。

l_k 维护线段树下标为 k 代表的区间中能被看见的楼房的个数(就是单纯只考虑这个区间),m_k 维护 k 区间中楼房的最大斜率。

考虑我们正在处理一个区间,线段树对应的下标为 k ,已经递归处理完他的左半边 L 和右半边 R,现在在进行合并。m_k=\max(m_L,m_R),这个是非常好想的,k 区间的最大斜率就是左右两半边取 max。问题就是 l_k 怎么合并,他不能单纯的等于 l_L+l_R,因为可能会出现右区间中的楼房被左区间的楼房挡住的情况,因此不能直接加起来。

很明显,我们需要在 R 区间中寻找有多少楼房不会被左边挡住。令 f(mk,k) 为在区间 k 中第一个不被 mk 斜率挡住的楼房及此楼房后面看得到的楼房的总数。返回之前的合并过程,有 l_k=l_L+f(m_L,R),因为 L 区间的贡献是无论如何都会产生的。故要在 R 中查找以第一个不会被左区间挡到的楼房开始的能看见的最多的楼房数。

现在考虑正在处理 f ,进入了 R 区间,而 R 区间又由两个小的区间 R_1R_2 构成。以下分三种情况:

  • 如果 m_R,说明左区间会把右区间全部挡完,返回 0
  • 如果 R 区间长度为 1,则看这栋楼是否会被挡,如果不会,返回 1,反之返回 0
  • 如果 m_{R_1},即右区间的左子区间会被挡完,那么就不管左区间了,递归查询右区间即 f(mk,R_2)
  • 如果 m_{R_1} > mk,即左子区间不会被挡完,那么显然右子区间产生的贡献即为 m_{R}-m_{R_2},即右区间的总个数(是已经处理完了的)减去左区间的贡献。然后还要递归查询左区间,因为不知道挡了多少,即 f(mk,R_1)

上述 pushup 过程的核心代码如下(f2 为上文的 mf1 为上文的 l):

int pushup(double mk,int i,int j,int k)
{
    if(f2[k]<=mk)//挡完
        return 0;
    if(a[i]>mk)//如果第一栋楼都能被看见
        return f1[k];//说明可以直接返回这个区间计算过的答案
    if(i==j)//区间长度为1的情况
        return f2[k]>mk;
    if(f2[L]<=mk)//如果左区间挡完
        return pushup(mk,M+1,j,R);//递归查询右区间
    return pushup(mk,i,M,L)+f1[k]-f1[L];//否则递归查询左区间再加上右区间的贡献
}

void change(int i,int j,int x,double d,int k)
{
    // balabala
    f2[k]=max(f2[L],f2[R]);
    f1[k]=f1[L]+pushup(f2[L],M+1,j,R);//左的全部贡献加上右还没被挡完的部分
    return;
}

了解了以上要点之后,不难发现每一次 pushup 的操作都为 O(\log n),故总复杂度为 O(m\log^2n)

代码:

#include <cstdio>
#include <cctype>
#include <algorithm>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)

using std::max;

const int maxn=1e5+5;

int f1[maxn<<2],n,m;
double f2[maxn<<2];//维护最大斜率的线段树
double a[maxn];//存储每栋楼的斜率

//快读省略

int pushup(double mk,int i,int j,int k)
{
    if(f2[k]<=mk)
        return 0;
    if(a[i]>mk)
        return f1[k];
    if(i==j)
        return f2[k]>mk;
    if(f2[L]<=mk)
        return pushup(mk,M+1,j,R);
    return pushup(mk,i,M,L)+f1[k]-f1[L];
}


void modify(int i,int j,int x,double d,int k)
{
    if(i==j&&i==x)
    {
        f1[k]=1;
        f2[k]=d;
        return;
    }
    if(x<=M)
        modify(i,M,x,d,L);
    if(x>M)
        modify(M+1,j,x,d,R);
    f2[k]=max(f2[L],f2[R]);
    f1[k]=f1[L]+pushup(f2[L],M+1,j,R);
    return;
}

int main()
{
    n=read(),m=read();
    int x,y;
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read();
        a[x]=(double)y/(double)x;
        modify(1,n,x,a[x],1);
        printf("%d\n",f1[1]);
    }
    return 0;
}
最后修改日期:2020年11月28日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。