Chlience

【题解】LOJ 2495 「AHOI / HNOI2018」转盘
Problem有排成一个圈的 $n$ 个物品,每个物品在 $T_i$ 时刻出现现在从零时刻任意一个点出发,每个时刻...
扫描右侧二维码阅读全文
06
2018/12

【题解】LOJ 2495 「AHOI / HNOI2018」转盘

Problem

有排成一个圈的 $n$ 个物品,每个物品在 $T_i$ 时刻出现

现在从零时刻任意一个点出发,每个时刻可以选择顺时针走一格或者留在原地,如果当时物品已经出现即可以拿走对应物品,问拿走所有物品的最短时间

有 $m$ 次修改,每次修改一个物品的出现时间,强制在线

Solution

先是比较 $naive$ 的想法

考虑从某个点开始的最短时间

ECharts (2).png

大概像这样,可能折回来 $y=0$ 回到原点我就没画了,因为两种情况其实是类似的,我们只讨论这一种

显然,可以转化为一种更加简单的方式:
先在原地等一等,然后再一次性走完

ECharts (1).png

因为保证了到达任意位置的时间必然比之前的方法到达该位置的时间要晚,前一种方式能够取到的点这样走必然也能取到

那么怎么确定从哪个点开始,又需要停多久呢?

若从 $i$ 号点开始,其需要等待的时间就是 $max\{t[j]-dis(i,j)\}\ j\in[1,n]$
其中 $dis$ 相当于从 $i$ 点一直走直到走到 $j$ 点需要的时间

因为是个环状,不如直接倍长,使得 $t[i+n] = t[i]$
那么需要等待的时间为 $max\{t[j]-(j-i)\}\ j\in[i,i+n-1]$
最终答案为 等待时间 + $n-1$

维护一个 $f[j] = t[j]-j$ 的数组,若需要查询某个点 $i$ 作为起点时的答案只需要求得 $n-1+i+max\{f[j]\}\ j\in[i,i+n-1]$

接下来 $too\ young$ 的我就不会做了...

上题解! (不对,这不就是题解么)

因为 $f[j]=t[j]-j>t[j]-j-n=t[j+n]$,原式可以化为 $n-1+i+max\{f[j]\}\ j\in[i,2n]$,也就是后缀最大值

这是一个有着奇妙偏序的最值问题

有一个很妙的用 线段树 来维护这个值的办法

首先,对于线段树某个节点 $x,[l,r]$
定义 $maxn[x]$ 为区间内最大值
定义 $val[x]$ 为 $min\{max\{i+f[j]\}\}\ i\in[l,mid],j\in[i,2n]$

初始化和建树啥的都很简单,就不多说了
考虑如何合并两个节点

设当前节点为 $x$,左儿子为 $L$,右儿子为 $R$

因为 $i$ 根本就不可能到右区间内所以 $val[R]$ 对 $val[x]$ 半毛钱贡献没有
但是其最大值 $maxn[R]$ 可能会影响左边的答案

那么考虑 $i$ 在左区间时的答案

  • 若 $L$ 右儿子的最大值 $maxn[rson[L]]$ 要大于等于 $maxn[R]$

    • $i$ 在 $L$ 左区间内的答案不被影响,因为其选择的 $max\{f[j]\}$ 必然满足 $max\{f[j]\}\geq maxn[rson[L]]\geq maxn[R]$。即 $val[L]$ 为 $i$ 在 $L$ 左区间的答案
    • $i$ 在 $L$ 右区间内的答案受 $maxn[R]$ 影响,递归处理
  • 反之

    • $i$ 在 $L$ 左区间内的答案受 $maxn[R]$ 影响,递归处理
    • $i$ 在 $L$ 右区间内的答案是一确定值 $mid + 1 + maxn[R]$ (此 $mid$ 是 $L$ 右区间的 $mid$,不要弄混),这是因为既然对于右区间内的任意 $i$,$max\{f[j]\}$ 均等于 $maxn[R]$,那么当然选个最小的 $i=mid+1$

1.png

这样,每次合并需要一次 $\log n$ 的递归,所以总复杂度为 $n\log^2 n+m\log^2n$,完美通过此题

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
const int N = 200010;

int t[N] , f[N];
int n , m , p , last;

struct Tree {
    int maxn[N << 2] , val[N << 2];
    int query(int x , int l , int r , int mx) {
        if(l == r) return l + max(mx , maxn[x]);
        if(mx <= maxn[R]) return min(val[x] , query(R , mid + 1 , r , mx));
        else return min(mid + mx + 1 , query(L , l , mid , mx));
    }
    void update(int x , int l , int r) {
        val[x] = query(L , l , mid , maxn[R]);
        maxn[x] = max(maxn[L] , maxn[R]);
    }
    void build(int x , int l , int r) {
        if(l == r) {
            maxn[x] = f[l];
            val[x] = l + f[l];
        }
        else {
            build(L , l , mid);
            build(R , mid + 1 , r);
            update(x , l , r);
        }
    }
    void change(int x , int l , int r , int pos) {
        if(l == r) {
            maxn[x] = f[l];
            val[x] = l + f[l];
        }
        else {
            if(pos <= mid) change(L , l , mid , pos);
            else change(R , mid + 1 , r , pos);
            update(x , l , r);
        }
    }
}tree;
int main() {
    n = read(); m = read(); p = read();
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%d" , & t[i]);
        f[i] = t[i] - i; f[i + n] = t[i] - i - n;
    }
    tree.build(1 , 1 , 2 * n);
    printf("%d\n" , last = tree.val[1] + n - 1);
    while(m -- ) {
        int x = read() , y = read();
        x ^= last * p;
        y ^= last * p;
        t[x] = y;
        f[x] = t[x] - x; f[x + n] = t[x] - x - n;
        tree.change(1 , 1 , 2 * n , x);
        tree.change(1 , 1 , 2 * n , x + n);
        printf("%d\n" ,  last = tree.val[1] + n - 1);
    }
    return 0;
}
Last modification:December 6th, 2018 at 08:34 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment