题意
给你绕成一圈的物品共 (n) 个 , 然后从其中一个开始选 , 每次有两种操作 ,
一是继续选择当前物品 , 二是选择这个后一个物品 .
选择后一个物品要求当前的时刻大于后一个的 (T_i) . 第一次选择的时候也要满足这个条件 .
求选完所有物品的最小时间 .
并且有 (m) 次修改 , 每次修改一个点的 (T_i) , 修改后询问当前的答案 .
部分点要求强制在线 .
((n le 100000 , m le 100000 , T_i le 100000))
题解
首先化环为链 .
然后我们枚举一个起点 , 然后考虑它的答案是什么 .
假设起点后面有点 (i) 那么令 (L_i) 为 (T_i) 与从 (i+1) 到当前终点的长度和 .
不难发现 其实就是这个序列中的 (L_i) 的最大值就是当前枚举起点的答案 .
这是因为 , 我们考虑从一个点后继续走 , 那么如果当前是最大的 , 就一下可以走到底 .
不是的话也没关系 , 因为我们就是当前起点求最大值耗费就行了.
然后我们要求最小的时间 .
写出式子就有
令 (P_i = T_i - i) .
我们简单整理就得到
此处后面 (max) 维护的终点可以到 (2n) . 为什么呢? 因为后面的会循环前面的 (T_i) 但 (i) 变大 , 所以不会影响 (max) 的答案.
如何考虑动态维护这个式子呢 ?
不难发现这个和 楼房重建 很像... 可考试的时候我并没有做过 , 只听过 ,
那么就愉快的只维护了后面 (max) 2333
我们考虑用线段树维护两个东西 假设当前区间为 ([l,r]) 中点为 (mid).
- (displaystyle min_{i=l}^{mid} {i + max_{j = i} ^{r} P_j}) .
- (displaystyle max_{i=l}^r P_i) .
第二个很好维护 , 主要是第一个如何维护 并且 为什么要维护 .
我们对于任意一个区间 考虑维护这个东西 , 需要将左边很多区间进行考虑 , 是否能优化当前答案 .
假设 (displaystyle max_{i=mid + 1}^{r} P_i = v) .
那么我们考虑另外一个区间 ([l', r']) 此处 (r' le mid) .
-
如果 (displaystyle v ge max_{i=mid'+1} ^{r'} P_i) 那么显然当前的最优答案在 ([l',mid'])
为什么呢 因为他们的 (max) 一样 那么下标越小越优 .
-
如果 (displaystyle v < max_{i=mid'+1} ^{r'} P_i) 那么当前的答案在左右两个区间都是可能的 ,
但左区间的答案我们之前已经计算过了并且 (max) 不会进行改变 所以可以直接用
右区间的我们继续递归下去计算就行了
有一个细节 就是到底了后 (l'+1+v) ((l' != mid)) 也可以是最优解
因为当前递归到最底层时的 (max) 可能很大 不够优秀..
为什么要维护这个呢 , 因为通过小的区间 , 我们可以逐渐维护出更大的区间的答案 , 并且不会漏掉情况 .
然后时间复杂度就是 (O(n log ^ 2 n)) .
([n+1,2n]) 的这个 (min) 没必要维护 常数可以除以 (2) ... (目前 (BZOJ rk2) )
代码
/**************************************************************
Problem: 5286
User: zjp_shadow
Language: C++
Result: Accepted
Time:3472 ms
Memory:17080 kb
****************************************************************/
#include<bits/stdc++.h>
#define For(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++ i)
#define Fordown(i, r, l) for (int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
inline bool chkmin(int &a, int b) { return b < a ? a = b, 1 : 0; }
inline bool chkmax(int &a, int b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * fh;
}
int n, m, p;
const int N = 1e5 + 1e3, inf = 0x3f3f3f3f;
#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r
struct Segment_Tree {
int maxv[N * 20], minv[N * 20];
int Query(int o, int l, int r, int qr, int qv) {
if (l == r) return min(l + max(maxv[o], qv), l == qr ? inf : l + 1 + qv);
int mid = (l + r) >> 1;
if (qv >= maxv[o << 1 | 1]) return Query(lson, qr, qv);
return min(minv[o], Query(rson, qr, qv));
}
void Update(int o, int l, int r, int up, int uv) {
if (l == r) { maxv[o] = uv; return; }
int mid = (l + r) >> 1;
if (up <= mid) Update(lson, up, uv); else Update(rson, up, uv);
maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
if (l <= n) minv[o] = Query(lson, mid, maxv[o << 1 | 1]);
}
} T;
int ans;
int main() {
n = read(); m = read(); p = read();
For (i, 1, n) {
int val = read();
T.Update(1, 1, n * 2, i, val - i);
T.Update(1, 1, n * 2, i + n, val - (i + n));
}
int x = 0, y = 0;
For (i, 0, m) {
if (i) x = read() ^ (p * ans), y = read() ^ (p * ans);
if (x) T.Update(1, 1, n * 2, x, y - x), T.Update(1, 1, n * 2, x + n, y - (x + n));
ans = T.minv[1] + n - 1;
printf ("%d
", ans);
}
return 0;
}