Qiuly

「HNOI/AHOI2018」转盘 线段树 luoguP4425
首先再来讲明一下题意:给定一个长度为 $n$ 的环,环上的每个点有一个权值 $T_i$ ,要求你从环上选中任意一个...
扫描右侧二维码阅读全文
24
2019/05

「HNOI/AHOI2018」转盘 线段树 luoguP4425

首先再来讲明一下题意:

给定一个长度为 $n$ 的环,环上的每个点有一个权值 $T_i$ ,要求你从环上选中任意一个点为起点开始,每个时间可以顺时钟到下一个点,或者停留不动。对于一个点,如果到这个点的时间大于等于了 $T_i$ ,那么这个点将被标记,问最少什么时候可以让所有物品都被标记。

可以发现,这个问题的答案跟以下问题的答案是等价的:

给定一个长度为 $n$ 的环,环上的每个点有一个权值 $T_i$ ,要求你从环上选中任意一个点为起点开始,,开始的时间为 $t$ ,每个时间可以逆时针到下一个点,或者停留不动。对于一个点,它将在 $T_i$ 时间损坏 ,求一个最小的 $t$ 使得我们能够在没有点损坏的情况下遍历所有点。

我们算一下每一个点离起点的距离,那么这个时候我们就可以在起点等,等一段时间后再出发,这样子我们转一圈就够了,这个方案显然是最优的。

我们断环为链,枚举起点 $s$ ,对于一个点 $i$ ,$s$ 到达 $i$ 的耗时显然是 $(i-s)$ ,那么我们如果想要等一段时间出发后正好标记该点,这一段等待的时间当然就是 $T_i-(i-s)$ 。我们对所有的点 $i$ 的 $T_i-(i-s)$ 取 $max$ ,最后的结果就是我们应该在 $s$ 等的时间。

那么很显然我们的答案为:

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[T_i-(i-s)] \}+n-1$$

$min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[T_i-(i-s)] \}$ 这显然是在选择一个最优的起点使得等待时间最小,$n-1$ 就是等待完后转一圈的时间。

这个时候暴力枚举就可以得到 $30$ 分。

不过我们继续:

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[T_i-i+s] \}+n-1$$

我们设 $A_i$ 为 $T_i-i$ 。

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,s+n-1]}[A_i+s] \}+n-1$$

假设现在有一对 $A_i,A_{i+n}$ ,我们可以发现 $A_{i+1}$ 是必然比 $A_i$ 小的,也就是说 $A_{s+n}$ 到 $A_{2n}$ 这一段数就算算进来也造不成影响。

也就是说原式跟这个式子是等价的:

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,2n]}[A_i+s] \}+n-1$$

发现 $max$ 里面 $s$ 并没有什么卵用,直接提出来。

$$Ans=min_{s \in [1,n]}\{ max_{i \in [s,2n]}A_i +s\}+n-1$$

这个的话......因为 $A_i$ 的值跟 $s$ 没有关系......所以......所以我们可以预处理一个 $ST$ 表......嗯......然后枚举 $s$ ......结果我们是 $O(n)$ 搞定???

哦哦哦作者脑抽了,这题是待修改的。

不过没关系,我们还有出路。

现在考虑用线段树来维护,假设结点 $x$ 代表的区间为 $l,r$ ,维护一个 $val[x]$ 表示区间 $[l,r]$ 中 $A_i$ 的最大值,这个是线段树基本操作不再赘述,然后再维护一个 $ans[x]$ 表示区间 $min_{s \in [l,mid]}\{ max_{i \in [s,r]} \}$ 。$1$ 号结点的区间为 $1,2n$ ,我们的答案就是 $ans[1]$ 。

那么怎么上传 $ans$ 呢。

我们对于 $[mid,r]$ 区间的最大值 $A_x$ ,这个 $A_x$ 显然可以 $O(1)$ 求出,然后再找到一个 $A_y$ ,表示当 $s$ 为 $y$ 的时候,整个 $[s,r]$ 的 $A_i$ 的最大值为 $A_x$ 。在寻找 $y$ 的时候顺便更新一下 $s\in [l,y-1]$ 的区间的答案就好。

当 $s\in [y,r]$ 的时候答案明显为 $A_x+s$ ,要满足最小嘛。

有关这一部分的代码实现:

inline void calc(int k,int l,int r,int Ax){
    if(l==r)return l+max(val[k],Ax);
    int mid=(l+r)>>1;
    else if(val[k<<1|1]>=Ax)return min(calc(k<<1|1,mid+1,r,Ax),ans[k<<1]);
    else return min(calc(k<<1,l,mid,Ax),(mid+1)+Ax);
}

我们来剖析一下代码。

inline void calc(int k,int l,int r,int Ax){

这一句表示当前的结点为 $k$ ,$k$ 代表的区间为 $l,r$ ,$Ax$ 为上文中的 $A_x$ 。

if(l==r)return l+max(val[k],Ax);

这个显然就是找到了 $y$ ,这个时候答案为 $A_x+s$ ,上文也讲了,这里的 $s$ 就是 $y$ 的位置,$A_x$ 已经在函数中了直接调用就好。但是为什么要取 $max$ 呢?因为怕 $A_y$ 是大于 $A_x$ 的! ,所以加个 $max$ 就好。

else if(val[k<<1|1]>=Ax)return min(calc(k<<1|1,mid+1,r,Ax),ans[k<<1]);

这个就是当前结点的右区间有比 $A_x$ 大的数,那么这个时候 $y$ 就不可能到左区间去了,不然的话 $[y,r]$ 中 $max\{A_i\}$ 就不是 $A_x$ 了,所以我们往右子树走。这个时候可以发现 $s$ 属于左区间的时候的答案为 $ans[k<<1]$ ,顺带更新一下。

else return min(calc(k<<1,l,mid,Ax),(mid+1)+Ax);

这个时候 $y$ 就是在左区间了,那么我们往左区间走,右区间的答案呢?右区间为 $[mid,r]$ ,显然这一段的最大值肯定都为 $A_x$ ——包括 $mid+1$ ,所以不要跟 $mid+1$ 取一下 $max$ 了——尽管第一句是与 $A_y$ 取了 $max$ 的。

这个时候因为要 $s$ 尽量的小,所以就是右区间的左端点——$mid+1$ 了。

这个时候 $pushup$ 就应该这么写:

inline void pushup(int x,int l,int r){
    val[x]=max(val[x<<1],val[x<<1|1]);
    int mid=(l+r)>>1;
    ans[x]=calc(x<<1,l,mid,val[x<<1|1]);
}

Code:

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
typedef long long ll;

const int N=4e5+2;
const int inf=1e9+9;

int n,m,p,lastans,a[N];

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct Seg_Tree{
    #define mid ((l+r)>>1)
    int ans[N<<2],val[N<<2];
    int calc(int x,int l,int r,int Mx){
        if(l==r)return l+max(val[x],Mx);
        if(val[x<<1|1]>=Mx)return min(calc(x<<1|1,mid+1,r,Mx),ans[x]);
        else return min(calc(x<<1,l,mid,Mx),mid+1+Mx);
    }
    inline void pushup(int x,int l,int r){
        val[x]=max(val[x<<1],val[x<<1|1]);
        ans[x]=calc(x<<1,l,mid,val[x<<1|1]);
    }
    inline void build(int x,int l,int r){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x,l,r);return;
    }
    inline void updata(int x,int l,int r,int pos){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        if(pos<=mid)updata(x<<1,l,mid,pos);
        else if(pos>mid)updata(x<<1|1,mid+1,r,pos);
        pushup(x,l,r);
    }
}T;

int main(){
    IN(n),IN(m),IN(p);
    for(int i=1;i<=n;++i)IN(a[i]),a[i+n]=a[i];
    for(int i=1;i<=(n<<1);++i)a[i]-=i;
    T.build(1,1,(n<<1));    
    lastans=T.ans[1]+n-1,printf("%d\n",lastans);
    for(int i=1;i<=m;++i){
        int x,y;IN(x),IN(y);
        if(p)x^=lastans,y^=lastans;
        a[x]=y-x,a[x+n]=y-x-n;
        T.updata(1,1,(n<<1),x),T.updata(1,1,(n<<1),x+n);
        printf("%d\n",lastans=T.ans[1]+n-1);
    }
    return 0;
}

但是这份代码是 TLE 的。

这玩意坑了我好久,你知道为什么 TLE 吗?

就是这个鬼东西!:

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))

这里的 $x$ 和 $y$ 是调用了两次的,然后我们发现 $calc$ 函数......

int calc(int x,int l,int r,int Mx){
    if(l==r)return l+max(val[x],Mx);
    if(val[x<<1|1]>=Mx)return min(calc(x<<1|1,mid+1,r,Mx),ans[x]);
    else return min(calc(x<<1,l,mid,Mx),mid+1+Mx);
}

$min$ 里面有 $calc$ 函数...........然后 $calc$ 函数调用了两次..........然后...........爆炸!

所以 $Qiuly$ 提醒您:代码千万条,时间第一条,$define$ 不规范,$OIer$ 两行泪 。

还是跟着 $std$ 走好嘿嘿嘿,$using\ namespace\ std$ 万岁!

最终 $AC$ 的代码。

Code:

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=4e5+2;
const int inf=1e9+9;

int n,m,p,lastans,a[N];

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct Seg_Tree{
    #define mid ((l+r)>>1)
    int ans[N<<2],val[N<<2];
    int calc(int x,int l,int r,int Mx){
        if(l==r)return l+max(val[x],Mx);
        if(val[x<<1|1]>=Mx)return min(calc(x<<1|1,mid+1,r,Mx),ans[x]);
        else return min(calc(x<<1,l,mid,Mx),mid+1+Mx);
    }
    inline void pushup(int x,int l,int r){
        val[x]=max(val[x<<1],val[x<<1|1]);
        ans[x]=calc(x<<1,l,mid,val[x<<1|1]);
    }
    inline void build(int x,int l,int r){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x,l,r);return;
    }
    inline void updata(int x,int l,int r,int pos){
        if(l==r){val[x]=a[l],ans[x]=a[l]+l;return;}
        if(pos<=mid)updata(x<<1,l,mid,pos);
        else if(pos>mid)updata(x<<1|1,mid+1,r,pos);
        pushup(x,l,r);
    }
}T;

int main(){
    IN(n),IN(m),IN(p);
    for(int i=1;i<=n;++i)IN(a[i]),a[i+n]=a[i];
    for(int i=1;i<=(n<<1);++i)a[i]-=i;
    T.build(1,1,(n<<1));    
    lastans=T.ans[1]+n-1,printf("%d\n",lastans);
    for(int i=1;i<=m;++i){
        int x,y;IN(x),IN(y);
        if(p)x^=lastans,y^=lastans;
        a[x]=y-x,a[x+n]=y-x-n;
        T.updata(1,1,(n<<1),x),T.updata(1,1,(n<<1),x+n);
        printf("%d\n",lastans=T.ans[1]+n-1);
    }
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 24 PM

发表评论