HNOI/AHOI2018转盘 分块

发表于 更新于 分类于 阅读次数：

[HNOI/AHOI2018]转盘 冷静分析一下：在原地呆一会再走比中间呆着优秀。倍长，钦定从$x$开始走，等待时间$s=\max_{i=x}^{i+n-1} \lbrace A_i - i + x \rbrace$。再冷静一下发现直接求到$2n$也是没问题的。 之后就是一个神秘转化了：反过来考虑$i$对$x$贡献，发现$A_i - i$单调的一段有贡献。就转化为了动态维护单调栈，动态维护最小值的问题。 考虑一种线段树做法：合并左右儿子，用右儿子的max在左边二分，找到合适的位置，再做一个区间查询。复杂度两个log。 还有一种高级分块方法：直接维护每一块的单调栈，询问的时候扫栈，考虑后面一块的max，在前面二分对应位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>

using std::cerr;
using std::endl;

const int N = 1e5 + 10, B = 500;

int n, m, op, A[N], ans;
int L[N], pos[N], block;
int stk[B][B], max[B], top_blk[B];
int min[B][B];

inline void modify(int blk) {
  int top = 0;
  for (int i = L[blk + 1] - 1; i >= L[blk]; --i) {
    if (!top  A[i] > A[stk[blk][top]])
      stk[blk][++top] = i;
  }
  max[blk] = A[stk[blk][top]];
  top_blk[blk] = top;
  for (int i = top; i >= 2; --i) {
    min[blk][i] = stk[blk][i] + A[stk[blk][i - 1]];
    if (i != top)
      min[blk][i] = std::min(min[blk][i], min[blk][i + 1]);
  }
}

struct Priority_Queue {
  std::priority_queue<int> que, del;
  inline void push(int x) {
    que.push(x);
  }
  inline void erase(int x) {
    del.push(x);
  }
  inline int top() {
    while (!que.empty() && !del.empty() && que.top() == del.top())
      que.pop(), del.pop();
    assert(!que.empty());
    return que.top();
  }
} que;

inline int query() {
  int Max = que.top(), ret = 1e9;
  for (int blk = pos[n]; blk; --blk) {
    if (max[blk] <= Max)
      continue;
    int l = 1, r = top_blk[blk], res = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (A[stk[blk][mid]] > Max)
        res = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    assert(res != -1);
    ret = std::min(ret, stk[blk][res] + Max);
    if (res != top_blk[blk])
      ret = std::min(ret, min[blk][res + 1]);
    Max = max[blk];
  }
  return ret + n;
}

int main() {
  freopen("data", "r", stdin);
  std::cin >> n >> m >> op;
  block = std::sqrt(n * std::log(n)) + 1;
  for (int i = 1; i <= n; ++i) {
    std::cin >> A[i];
    A[i] -= i;
    pos[i] = (i - 1) / block + 1;
    if (pos[i] != pos[i - 1])
      L[pos[i]] = i;
    que.push(A[i] - n);
  }
  pos[n + 1] = pos[n] + 1;
  L[pos[n + 1]] = n + 1;
  for (int i = 1; i <= pos[n]; ++i)
    modify(i);
  ans = query();
  std::cout << ans << '\n';
  // exit(0);
  while (m--) {
    int x, y; std::cin >> x >> y;
    if (op) x ^= ans, y ^= ans;
    que.erase(A[x] - n);
    A[x] = y - x;
    que.push(A[x] - n);
    modify(pos[x]);
    ans = query();
    std::cout << ans << '\n';
  }
  return 0;
}