题解 P4425 【[HNOI/AHOI2018]转盘】
Nemlit
2019-10-12 20:01:12
~~颂魔眼中的一眼题我大湖南竟无一人$AC$~~
首先我们考虑一个性质:我们肯定存在一种最优解,满足从某个点出发,一直往前走,不停下来。
证明:我们假设存在一种最优解,是在$t_i$的时候到达$a$点,那么我肯定会在$t_i - x(x≥1)$的时间会到达$a - 1$号点
我们假设$x != 1$,即我们会在$a-1$点进行停留,此时那么我们到达$a - 2$号点的时间$<t_i - 2$,到达$a-3$号点的时间$<t_i - 3$
那么如果我有一个点$a - y$是在$t_i - y$时刻出现,那么我们不能取到这个点,必须要重新转一圈
那么如果$x = 1$,且每一次走都没停下来,我们可以保证我们在$x!=1$经过该点后经过该点
所以说如果$x!=1$可以经过的所有点我们肯定在$x==1$的情况下都能经过,而且$x==1$情况下的一些点,$x != 1$不一定能经过,所以我们肯定每一次取$x==1$是一种最优情况
然后我们考虑进一步转化题意:假设我在一个点,从$T_i$时刻出发,满足转一圈刚好标记所有点,那么我们$T_i$以前的时间实际上是没有用的
由于环不好处理,而且转化后我们保证只要走一圈,所以我们可以断环成链
于是我们可以考虑,找到一个最好的起点$i$,找到最好的$T_i$,使得从i点在$T_i$时刻出发答案最优,即我们要求这个式子:$min(T_i+n)$其中满足对于任意的$x$,$T_i≥t_x-x+i$
即我们要求:$min_{i=1}^n(n + max_{x=i+1}^{2*n}(i-x + t_x))=min_{i=1}^n(n+i+max_{x=i+1}^{2*n}(x-t_x))$
所以我们枚举每一个起点,找到最大的$t_x-x$,用线段树维护,单次操作复杂度为$O(NlogN)$,现在问题要考虑怎么修改
令$a_i=t_i-i$,所以原式变成$n+min_{i=1}^n(max_{x=i+1}^{2*n}(a_x)+i)$
不难发现,$max_{x=i+1}^{i+n}(a_x)$是单调不增的。于是,我们维护一个单调栈,对于每一个$max_{x=i+1}^{i+n}(a_x)$连续的一段,找到一个最小的$i$即可,单调栈可以用线段树来维护([详见我楼房重建的题解](https://www.cnblogs.com/bcoier/p/10293075.html)),把楼房重建的求和改成$max$就行了,于是复杂度就变成了$O(Nlog^2N)$
## $Code:$
```
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
#define ls k * 2
#define rs k * 2 + 1
#define maxn 100005
int n, m, p, last, a[maxn << 1], ma[maxn << 3], ans[maxn << 3];
int query(int k, int l, int r, int v) {
if(l == r) return l + max(v, ma[k]);
int mid = (l + r) >> 1;
if(ma[rs] >= v) return min(ans[k], query(rs, mid + 1, r, v));
return min(mid + v + 1, query(ls, l, mid, v));
}
inline void updata(int k, int l, int r, int mid) {
ma[k] = max(ma[ls], ma[rs]), ans[k] = query(ls, l, mid, ma[rs]);
}
void modify(int k, int l, int r, int ll) {
if(l == r) return (void)(ans[k] = a[l] + l, ma[k] = a[l]);
int mid = (l + r) >> 1;
if(ll <= mid) modify(ls, l, mid, ll);
else modify(rs, mid + 1, r, ll);
updata(k, l, r, mid);
}
void build(int k, int l, int r) {
if(l == r) return (void)(ans[k] = a[l] + l, ma[k] = a[l]);
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r), updata(k, l, r, mid);
}
int main() {
n = read(), m = read(), p = read();
rep(i, 1, n) a[i] = read() - i, a[i + n] = a[i] - n;
build(1, 1, n * 2);
printf("%d\n", last = ans[1] + n - 1);
rep(i, 1, m) {
int x = read() ^ (p * last), y = read() ^ (p * last);
a[x] = y - x, a[x + n] = y - x - n, modify(1, 1, 2 * n, x), modify(1, 1, 2 * n, x + n);
printf("%d\n", last = ans[1] + n - 1);
}
return 0;
}
```