树状数组。

Table of Contents

  1. Description
  2. Solution

Description

维护一个长度为$n$的序列，一开始都是0，支持以下两种操作：

$U k a$ 将序列中第$k$个数修改为$a$。

$Z c s$ 在这个序列上，每次选出$c$个正数，并将它们都减去$1$，询问能否进行$s$次操作。

每次询问独立，即每次询问不会对序列进行修改。

Solution

记录一个 $C = \sum_{a_i \ge s}{1}$, $S = \sum_{a_i < s}{a_i}$.

那么可行的充要条件就是：$S \ge (c - C) \times s$.

我们来证明一下.

如果大于等于$s$的数字有超过$c$个, 那么我们直接取就可以了.

如果不够$c$个, 也就是我们需要选择$c - C$个较小的数字, 我们将$a_i$视为她最多被选中的次数, 由于$S \ge (c - C) \times s$, 所以$\frac{S}{s} \ge c - C$, 也就是说, 总有多于我们需要的数字备选. 当我们选择一次后, 不等式变为 $\frac{S - s}{s - 1} \ge c - C$, 这时我们有证明：

设常量$a = c - C$,

则$\frac{S - s}{s} = \frac{S}{s} - 1 \ge a - 1$,

由于$\frac{S - s}{s - 1} > \frac{S - s}{s}$,

所以$\frac{S-s}{s-1} > a - 1 \ge a$.

Q.E.D.

若不满足上不等式,可证无法选出足够的数字.

所以用两个树状数组分别维护个数和权值和就可以了.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long ll;

const int max_n = int(1e+6 + 5);

struct Option {
  int x, y, typ;
}q[max_n];
int n, m, a[max_n];
int cpy[max_n], tot, sum, rk[max_n];
int val[max_n];
ll bs[max_n], bv[max_n];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline void add(int x, int c, ll *b) {
  for (; x <= sum + 1; x += (x & -x))
    b[x] += (ll)c;
}
inline ll query(int x, ll *b) {
  ll ret = 0;
  for (; x; x -= (x & -x)) ret += b[x];
  return ret;
}

int main() {
  n = rd(); m = rd();
  char *line = new char[5];
  for (int i = 1; i <= m; ++i) {
    scanf("%s%d%d", line, &q[i].x, &q[i].y);
    if (line[0] == 'U') {
      q[i].typ = ++tot;
      cpy[tot] = rk[tot] = q[i].y;
    } else {
      q[i].typ = -1;
    }
  }
  sort(cpy + 1, cpy + 1 + tot);
  sum = int(unique(cpy + 1, cpy + 1 + tot) - (cpy + 1));
  for (int i = 1; i <= tot; ++i)
    rk[i] = int(lower_bound(cpy + 1, cpy + 1 + sum, rk[i]) - cpy);
  for (int i = 1; i <= m; ++i) 
    if (~q[i].typ) 
      q[i].y = rk[q[i].typ];
  for (int i = 1; i <= m; ++i) {
    if (~q[i].typ) {
      if (val[q[i].x] > 0) {
        int rkk = lower_bound(cpy + 1, cpy + 1 + sum, val[q[i].x]) - cpy;
        add(rkk + 1, -1, bs);
        add(rkk + 1, -val[q[i].x], bv);
      }
      val[q[i].x] = cpy[q[i].y];
      if (val[q[i].x] > 0) {
        add(q[i].y + 1, 1, bs);
        add(q[i].y + 1, cpy[q[i].y], bv);
      }
    } else {
      int rkk = upper_bound(cpy + 1, cpy + 1 + sum, q[i].y) - cpy - 1;
      ll cnt = query(sum + 1, bs) - query(rkk + 1, bs);
      ll lower_sum = query(rkk + 1, bv);
      if (lower_sum >= (q[i].x - cnt) * (ll)q[i].y) puts("TAK");
      else puts("NIE");
    }
  }
  return 0;
}