题解：P11733 [集训队互测 2015] 上帝之手

· · 题解

[集训队互测 2015] 上帝之手 题解

博客园：[集训队互测 2015] 上帝之手 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

线段树，分块。

分析

约定

定义更换：l_i\to lim_i,d_i\to del_i。

定义查询 F(l,r,x)（如果 x 空缺，默认为 lim_{l-1}）表示 x 一直做 \to \min\{ x+del_i,lim_i \} 得到的答案。

快速查询

假设给定的是 F(l,r)，那么我们就要求出：

\min_{i=l}^{r+1} \{ lim_{i-1} + \sum_{j=i}^r del_j\}

设 Del_i= \sum_{j=1}^i del_i,D_i = lim_i-Del_i，原式化为：

\min_{i=l}^{r+1} \{ lim_{i-1} + Del_r - Del_{i-1}\} \\ = \min_{i=l-1}^{r} D_{i} + Del_r\\

如果是 F(l,r,x) 其实也一样，查询的是：

\min \{ x - Del_{l-1},\min_{i=l}^{r} D_{i} \} + Del_r \\

线段树维护，单次查询 O(\log{n})。

询问 1

给定 l,r,k，求 F(j,r),j\in[l,r] 中第 k 大的。

那么很容易看出 F(j,r) 具有单调不减的性质，所以答案就是 F(r-k+1,r)。

询问 2

给定 l,r,k，求 F(j,r,k),j\in[l,r] 中最大的。

考虑把定义式拉出来，就是：

F(j,r,k)=\min \{ k - Del_{j-1},\min_{i=j}^{r} D_{i} \} + Del_r \\

设 f(j) = k - Del_{j-1},g(j) = \min_{i=j}^{r} D_{i}，则有 f(j) 非严格单调递减，g(j) 非严格单调递增。

拆掉外层的 \min，二分出边界，分别求出 f(j)\le g(j) 和 g(j)\le f(j) 时的答案即可。二分套线段树可以做到 O(\log^2{n})。

考虑满足 g(j)\le f(j)。则有：

\begin{aligned} \min_{i=j}^{r} D_{i} & \le k - Del_{j-1}\\ \min_{i=j}^{r} D_{i} + Del_{j-1} & \le k \\ \end{aligned}

故也可以线段树上二分做到复杂度 O(\log{n})（不过其实没有必要）。

询问 3

给定 l,r，求 F(j,r),j\in[l,r] 总共有多少种本质不同的值。

我们还是把定义式拉出来看：

F(j,r) = \min_{i=j-1}^{r} D_{i} + Del_r\\

发现其实是求 \min_{i=j-1}^{r} D_{i} 本质不同值的个数，也就是 D 的区间严格后缀最小值个数，变成 P4198 楼房重建 - 洛谷 (luogu.com.cn) 这题了。注意特判一下 D_r。

复杂度 O(\log^2{n})。

代码

总复杂度 O(n\log{n}+m\log^2{n})。

constexpr int N(1e5+10);

int n,Q;
int del[N],lim[N];
struct SEG {
    struct node {
        int D,C;
        node(int D=0,int C=0):D(D),C(C) {}
    } tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
    void Up(int p,int l,int r) { tr[p].D=min(tr[ls].D,tr[rs].D),tr[p].C=Count(tr[rs].D,ls,l,mid); }

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

    void Update(int x,int p=1,int l=0,int r=n) {
        if(l==r)return tr[p]=node(lim[l]-del[l],0),void();
        return x<=mid?Update(x,ls,l,mid):Update(x,rs,mid+1,r),Up(p,l,r);
    }

    int Min(int L,int R,int p=1,int l=0,int r=n) {
        if(L<=l&&r<=R)return tr[p].D;
        if(R<=mid)return Min(L,R,ls,l,mid);
        if(mid<L)return Min(L,R,rs,mid+1,r);
        return min(Min(L,R,ls,l,mid),Min(L,R,rs,mid+1,r));
    }

    int Count(int k,int p=1,int l=0,int r=n) {
        if(tr[p].D>=k)return 0;
        if(l==r)return tr[p].D<k;
        return tr[rs].D>=k?Count(k,ls,l,mid):tr[p].C+Count(k,rs,mid+1,r);
    }

    int Query(int L,int R,int &k,int p=1,int l=0,int r=n) {
        if(L<=l&&r<=R) {
            int res(Count(k,p,l,r));
            return tomin(k,tr[p].D),res;
        }
        if(mid<L)return Query(L,R,k,rs,mid+1,r);
        if(R<=mid)return Query(L,R,k,ls,l,mid);
        return Query(L,R,k,rs,mid+1,r)+Query(L,R,k,ls,l,mid);
    }
#undef ls
#undef rs
#undef mid
} seg;

void Change(int x,int d) { lim[x]=d,seg.Update(x); }

int Query1(int r,int k) { return seg.Min(r-k,r)+del[r]; }

int Query2(int l,int r,int k) {
    auto f=[&](int j) { return k-del[j-1]; };
    auto g=[&](int j) { return seg.Min(j,r); };
    int res(l-1);
    for(int L(l),R(r),mid((L+R)>>1); L<=R; mid=(L+R)>>1)g(mid)<=f(mid)?res=mid,L=mid+1:R=mid-1;
    int ans(0);
    if(res>=l)tomax(ans,g(res)+del[r]);
    if(res<r)tomax(ans,f(res+1)+del[r]);
    return ans;
}

int Query3(int l,int r) {
    if(l==r)return 1;
    int k(INF),res(seg.Query(l-1,r,k));
    if(lim[r]-del[r]>lim[r-1]-del[r-1])--res;
    return res;
}

signed main() {
    /*DE("Input");*/
    I(n,Q);
    FOR(i,1,n)I(del[i]);
    FOR(i,0,n)I(lim[i]);
    /*DE("Init");*/
    FOR(i,1,n)del[i]+=del[i-1];
    seg.Build();
    /*DE("Query");*/
    while(Q--) {
        int ty;
        I(ty);
        if(!ty) {
            int x,d;
            I(x,d),Change(x,d);
        } else if(ty==1) {
            int l,r,k;
            I(l,r,k),printf("%d\n",Query1(r,k));
        } else if(ty==2) {
            int l,r,k;
            I(l,r,k),printf("%d\n",Query2(l,r,k));
        } else {
            int l,r;
            I(l,r),printf("%d\n",Query3(l,r));
        }
    }
    return 0;
}