Skip to content

「POI2015」Logistyka

题解732 字
# 洛谷 # POI # 数据结构 # 树状数组 # 2015
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

  1. U k a 将序列中第 kk 个数修改为 aa。
  2. Z c s 在这个序列上，每次选出 cc 个正数，并将它们都减去 11，询问能否进行 ss 次操作。

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

#输入格式

第一行包含两个正整数 n,mn, m，分别表示序列长度和操作次数。

接下来 mm 行为 mm 个操作。

#输出格式

包含若干行，对于每个 Z 询问，若可行，输出 TAK，否则输出 NIE。

#输入输出样例

样例输入 #1

3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1

样例输出 #1

NIE
TAK
NIE
TAK

#数据范围与约定

对于 100%100\% 的数据，1≤n,m≤1061 \leq n, m \leq 10^6，1≤k,c≤n1 \leq k, c \leq n，0≤a≤1090 \leq a \leq 10^9，1≤s≤1091 \leq s \leq 10^9。

#思路

本题的答案实际上和序列无关，因此可以将序列看作一个集合来处理。设 ≥s\geq s 的数有 xx 个，<s< s 的数和为 sum\mathit{sum}，有结论如下：

如果无法满足 sum≥(c−x)×s\mathit{sum} \geq (c - x) \times s 则操作一定不能成功，满足后要证明每次取有至少 cc 个数。那么考虑小于 ss 的数最少的时候有 ⌈sums−1⌉\lceil \frac{\mathit{sum}}{s - 1} \rceil 个，如果满足 sum≥(c−x)×s\mathit{sum} \geq (c - x) \times s，则 ⌈sums−1⌉>c−x\lceil \frac{\mathit{sum}}{s - 1} \rceil > c - x，此时一定有解。

#代码

C++
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
#include <algorithm>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e6 + 5;

int n, m, x[N], y[N], a[N], p, nums[N];
char op[N];

long long c1[N], c2[N];

inline int lowbit(int x) {
    return x & -x;
}

void add(long long *c, int x, int y) {
    for (; x <= n + m; x += lowbit(x)) c[x] += y;
}

long long sum(long long *c, int x) {
    long long ans = 0;
    for (; x; x -= lowbit(x)) ans += c[x];
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> op[i] >> x[i] >> y[i];

        nums[++p] = y[i];
    }

    std::sort(nums + 1, nums + 1 + p);
    p = std::unique(nums + 1, nums + 1 + p) - nums - 1;

    for (int i = 1, k; i <= m; i++) {
        y[i] = std::lower_bound(nums + 1, nums + 1 + p, y[i]) - nums;
        if (op[i] == 'U') {
            if (k = a[x[i]]) {
                add(c1, k, -1);
                add(c2, k, -nums[k]);
            }
            k = a[x[i]] = y[i];
            add(c1, k, 1);
            add(c2, k, nums[k]);
        } else {  // op[i] == 'Z'
            int c = sum(c1, p) - sum(c1, y[i] - 1);
            long long s = sum(c2, y[i] - 1);
            cout << (s >= 1ll * (x[i] - c) * nums[y[i]] ? "TAK" : "NIE") << endl;
        }
    }

    return 0;
}