M_sea

洛谷4425 [HNOI2018]转盘
LuoguBZOJ分析神仙题,不看题解不会做。推荐阅读转换一下题意:假设你 $t$ 时刻在某个点,每次可以向前走或...
扫描右侧二维码阅读全文
11
2019/03

洛谷4425 [HNOI2018]转盘

Luogu

BZOJ

分析

神仙题,不看题解不会做

推荐阅读


转换一下题意:

假设你 $t$ 时刻在某个点,每次可以向前走或者留在原地,然后 $t$ 减 $1$ 。

每个点在 $T_i$ 时间消失,求一个最小的 $t$ 使得在所有点都消失前访问所有点。

这样子的话,你留在原地显然是不优的。

考虑破环为链,枚举起点 $i\in [n,2n)$ ,显然对于所有的 $j\in(i-n,i]$ 都要满足 $t-(i-j)\geq T_j$ ,化简后得到 $t_\min=\max\{T_j-j\}+i$ 。

这样就可以 $O(n\log n)$ 算出答案了。

设 $a_i=T_i-i$ ,那么 $ans=\min\limits_{i=n}^{2n-1}\{\max\limits_{j=i-n+1}^i a_j+i\}$ 。

稍微变一下可以得到 $ans=\min\limits_{i=1}^n\{\max\limits_{j=i}^{2n}a_j+i\}+n-1$ 。

这样子对于每个 $i$ ,算出后缀最大值就能算出答案。然而这样子还是 $O(n\log n)$ 的。

既然考虑 $i$ 不行,那就考虑 $j$ 。

  • 如果 $j$ 是后缀最大值,那么找到 $j$ 前面第一个权值大于 $a_j$ 的 $a_i$ ,答案就是 $a_j+i+1$ 。
  • 否则,它的答案与后缀最大值的答案一样。

那么我们可以从后往前对这个序列维护一个单调上升的栈。

设栈中的元素为 $s_0,s_1,...,s_k$ , $j$ 满足 $s_{j-1}<n\leq s_j$ ,那么可以得到 $ans=\min\limits_{i=1}^j\{a_{s_i}+s_{i-1}\}+n$ 。

可以用线段树来维护这个单调栈(和楼房重建那题一样)。这样子就做完了。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int inf=0x3f3f3f3f;

int n,m,tp;
int a[N];

struct segment_tree {
    int mx[N<<2],s[N<<2];
    
#define ls (o<<1)
#define rs (o<<1|1)
    
    inline int query(int o,int l,int r,int k) {
        if (l==r) { return mx[o]>k?k+l:inf; }
        int mid=(l+r)>>1;
        if (mx[rs]<=k) return query(ls,l,mid,k);
        else return min(s[o],query(rs,mid+1,r,k));
    }
    
    inline void pushup(int o,int l,int r) {
        mx[o]=max(mx[ls],mx[rs]);
        s[o]=query(ls,l,(l+r)>>1,mx[rs]);
    }   
    
    inline void build(int o,int l,int r) {
        if (l==r) { mx[o]=a[l]-l; return; }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(o,l,r);
    }

    inline void update(int o,int l,int r,int p,int w) {
        if (l==r) { mx[o]=w-l; return; }
        int mid=(l+r)>>1;
        if (p<=mid) update(ls,l,mid,p,w);
        else update(rs,mid+1,r,p,w);
        pushup(o,l,r);
    }
    
#undef ls
#undef rs
    
} T;

int main() {
    n=read(),m=read(),tp=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    T.build(1,1,n); int lastans=T.query(1,1,n,T.mx[1]-n)+n;
    printf("%d\n",lastans);
    while (m--) {
        int x=read(),y=read();
        if (tp) x^=lastans,y^=lastans;
        T.update(1,1,n,x,y); lastans=T.query(1,1,n,T.mx[1]-n)+n;
        printf("%d\n",lastans);
    }
    return 0;
最后修改:2019 年 05 月 26 日 09 : 11 PM

发表评论