[ZJOI2007] 报表统计 题解

Description

link

Solution

显然是道 DS。

想到建两个个平衡树。一个用来维护所有数的最小差值，插入 xx 时，找到 xx 的前驱和后继更新答案即可。

另一个用来维护相邻数的最小差值。假设操作时在 kk 后插入 xx，那么 lst[k]lst[k] 和 a[k+1]a[k+1] 就不再相邻，需要删除，然后插入 ∣lst[k]−x∣|lst[k]-x| 和 ∣x−a[k+1]∣|x-a[k+1]|，然后将 lst[k]lst[k] 更新。

用 Splay 写就可以做到均摊 O(log⁡n)O(\log n)，总复杂度 O((n+m)log⁡n)O((n+m)\log n)，但有个巨大的常数，所以不开 O2 过不了。（用 multiset 可过）

Code

Splay
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include <bits/stdc++.h>

#ifdef ORZXKR
#include <debug.h>
#else
#define debug(...) 1
#endif

using namespace std;

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
bool read(char &x) {
  while ((x = getc()) == ' ' || x == '\n' || x == '\r');
  return x != EOF;
}
bool read(char *x) {
  while ((*x = getc()) == '\n' || *x == ' ' || *x == '\r');
  if (*x == EOF) return 0;
  while (!(*x == '\n' || *x == ' ' || *x == '\r' || *x == EOF)) *(++x) = getc();
  *x = 0;
  return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }

char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

const int kMaxN = 2e6 + 5;

class Splay {
/********** Need **********
 * Insert
 * Delete
 * GetPre
 * GetNext
 * GetMin
 ********** Need **********/
  public:
    int newnode(int x) {
      val[++tot] = x, sz[tot] = cnt[tot] = 1;
      return tot;
    }
    void pushup(int x) {
      sz[x] = sz[ch[x][0]] + cnt[x] + sz[ch[x][1]];
    }
    int get(int x) {
      return x == ch[fa[x]][1];
    }
    void clear(int x) {
      sz[x] = cnt[x] = val[x] = ch[x][0] = ch[x][1] = fa[x] = 0;
    }
    void rotate(int x) {
      int fl = get(x), y = fa[x], z = fa[y];
      ch[y][fl] = ch[x][fl ^ 1];
      if (ch[x][fl ^ 1]) fa[ch[x][fl ^ 1]] = y;
      ch[x][fl ^ 1] = y;
      if (z) ch[z][get(y)] = x;
      fa[y] = x, fa[x] = z;
      pushup(y), pushup(x);
    }
    void splay(int x) {
      for (int y = fa[x]; y = fa[x], y; rotate(x)) {
        if (fa[y]) rotate(get(x) == get(y) ? y : x);
      }
      rt = x;
    }
    void ins(int x) {
      if (!rt) {
        rt = newnode(x), pushup(rt);
        return ;
      }
      for (int cur = rt, f = 0; ; ) {
        if (val[cur] == x) {
          ++cnt[cur], pushup(cur), pushup(f);
          return splay(cur);
        }
        f = cur;
        cur = ch[cur][val[cur] < x];
        if (!cur) {
          cur = newnode(x), fa[cur] = f, ch[f][val[f] < x] = cur;
          pushup(cur), pushup(f);
          return splay(cur);
        }
      }
    }
    int getrk(int x) {
      int ret = 0;
      for (int cur = rt; cur; ) {
        if (x < val[cur]) {
          cur = ch[cur][0];
        } else if (x == val[cur]) {
          ret += sz[ch[cur][0]] + 1, splay(cur);
          return ret;
        } else {
          ret += sz[ch[cur][0]] + cnt[cur];
          cur = ch[cur][1];
        }
      }
    }
    void _getpre() {
      int cur;
      for (cur = ch[rt][0]; ch[cur][1]; cur = ch[cur][1]) {}
      return splay(cur);
    }
    void del(int x) {
      getrk(x);
      if (cnt[rt] > 1) {
        --cnt[rt];
        return pushup(rt);
      }
      if (!ch[rt][0] && !ch[rt][1]) {
        clear(rt), rt = 0;
        return ;
      } else if (!ch[rt][0]) {
        int tmp = rt;
        rt = ch[rt][1], fa[rt] = 0;
        return clear(tmp);
      } else if (!ch[rt][1]) {
        int tmp = rt;
        rt = ch[rt][0], fa[rt] = 0;
        return clear(tmp);
      }
      int tmp = rt;
      _getpre();
      fa[ch[tmp][1]] = rt, ch[rt][1] = ch[tmp][1];
      return clear(tmp), pushup(rt);
    }
    int getpre(int x) {
      ins(x);
      if (cnt[rt] > 1) return del(x), x;
      if (!ch[rt][0]) return del(x), -1;
      int ret, cur;
      for (cur = ch[rt][0]; ch[cur][1]; cur = ch[cur][1]) {}
      ret = val[cur], splay(cur);
      del(x);
      return ret;
    }
    int getnxt(int x) {
      ins(x);
      if (cnt[rt] > 1) return del(x), x;
      if (!ch[rt][1]) return del(x), -1;
      int ret, cur;
      for (cur = ch[rt][1]; ch[cur][0]; cur = ch[cur][0]) {}
      ret = val[cur], splay(cur);        
      del(x);
      return ret;
    }
    int getmin() {
      int cur;
      if (!ch[rt][0]) return val[rt];
      for (cur = ch[rt][0]; ch[cur][0]; cur = ch[cur][0]) {}
      return val[cur];
    }
  private:
    int rt, tot, sz[kMaxN], cnt[kMaxN], val[kMaxN], ch[kMaxN][2], fa[kMaxN];
} s1, s2;

int n, m, ans2;
int a[kMaxN], b[kMaxN];
vector<int> v[kMaxN];

int main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  read(n, m);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    b[i] = a[i];
    v[i].emplace_back(b[i]);
    s1.ins(a[i]);
    if (i > 1) s2.ins(abs(a[i] - a[i - 1]));
  }
  ans2 = INT_MAX;
  sort(b + 1, b + 1 + n);
  for (int i = 1; i < n; ++i) {
    ans2 = min(ans2, b[i + 1] - b[i]);
  }
  while (m--) {
    char op[10]; int x, k;
    read(op);
    if (op[0] == 'I') { // INSERT
      read(x, k);
      int lst = v[x][v[x].size() - 1], pre = s1.getpre(k), nxt = s1.getnxt(k);
      if (x != n) s2.del(abs(a[x + 1] - lst)), s2.ins(abs(k - a[x + 1]));
      s2.ins(abs(k - lst));
      v[x].emplace_back(k);
      if (~pre) ans2 = min(ans2, k - pre);
      if (~nxt) ans2 = min(ans2, nxt - k);
      s1.ins(k);
    } else if (op[4] == 'G') { // MIN_GAP
      write(s2.getmin(), '\n');
    } else { // MIN_SORT_GAP
      write(ans2, '\n');
    }
  }
  return 0;
}
multiset
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
97
98
#include <bits/stdc++.h>

#ifdef ORZXKR
#include <debug.h>
#else
#define debug(...) 1
#endif

using namespace std;

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
bool read(char &x) {
  while ((x = getc()) == ' ' || x == '\n' || x == '\r');
  return x != EOF;
}
bool read(char *x) {
  while ((*x = getc()) == '\n' || *x == ' ' || *x == '\r');
  if (*x == EOF) return 0;
  while (!(*x == '\n' || *x == ' ' || *x == '\r' || *x == EOF)) *(++x) = getc();
  *x = 0;
  return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }

char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

const int kMaxN = 5e5 + 5;

int n, m, ans2;
int a[kMaxN], b[kMaxN];
vector<int> v[kMaxN];
multiset<int> s1, s2;

int main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  read(n, m);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    b[i] = a[i];
    v[i].emplace_back(a[i]), s1.emplace(a[i]);
  }
  ans2 = 1e9;
  sort(b + 1, b + 1 + n);
  for (int i = 1; i <= n - 1; ++i) {
    s2.emplace(abs(a[i + 1] - a[i]));
    ans2 = min(ans2, abs(b[i + 1] - b[i]));
  }
  while (m--) {
    char op[10]; int x, k;
    read(op);
    if (op[0] == 'I') { // INSERT
      read(x, k);
      int lst = v[x][v[x].size() - 1];
      auto it = s1.lower_bound(k);
      if (it != s1.end()) ans2 = min(ans2, *it - k);
      if (it != s1.begin()) --it, ans2 = min(ans2, k - *it);
      auto ii = s2.lower_bound(abs(a[x + 1] - lst));
      if (ii != s2.end()) s2.erase(ii);
      s2.emplace(abs(k - lst));
      if (x != n) s2.emplace(abs(k - a[x + 1]));
      s1.emplace(k), v[x].emplace_back(k);
    } else if (op[4] == 'G') { // MIN_GAP
      write(*s2.begin(), '\n');
    } else { // MIN_SORT_GAP
      write(ans2, '\n');
    }
  }
  return 0;
}
[ZJOI2007] 报表统计 题解
https://sobaliuziao.github.io/2022/10/13/post/4b2f6b3a.html
作者
Egg_laying_master
发布于
2022年10月13日
许可协议