QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182720#6701. BaoBao Loves Readingucup-team004AC ✓101ms4792kbC++201.8kb2023-09-18 14:30:352023-09-18 14:30:35

Judging History

你现在查看的是最新测评结果

  • [2023-09-18 14:30:35]
  • 评测
  • 测评结果:AC
  • 用时:101ms
  • 内存:4792kb
  • [2023-09-18 14:30:35]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n = 0) {
        init(n);
    }
    
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
    
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
    }
    
    Fenwick<int> fen(n);
    
    std::vector<int> ans(n + 1);
    
    std::vector<int> lst(n, -1);
    for (int i = 0; i < n; i++) {
        if (lst[a[i]] == -1) {
            ans[n]++;
        } else {
            ans[fen.rangeSum(lst[a[i]], i) - 1]++;
            fen.add(lst[a[i]], -1);
        }
        lst[a[i]] = i;
        fen.add(i, 1);
    }
    
    for (int i = n - 1; i >= 1; i--) {
        ans[i] += ans[i + 1];
    }
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

1
7
4 3 4 2 3 1 4

output:

7 6 5 4 4 4 4

result:

ok single line: '7 6 5 4 4 4 4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

100
73
45 45 2 2 2 45 35 45 16 35 16 45 35 2 16 16 45 2 45 45 16 35 35 16 35 35 2 2 2 35 45 35 45 35 16 35 2 2 16 35 16 45 45 16 45 2 16 16 35 16 45 16 45 45 16 16 35 35 35 35 45 45 45 35 16 16 16 2 16 16 35 16 2
83
78 52 7 35 33 82 51 27 45 34 17 51 55 25 26 11 52 41 25 41 13 46 33 83 83 7 40 51 33...

output:

51 30 17 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
80 77 74 73 69 68 66 64 61 61 59 56 53 49 47 47 44 42 39 38 36 36 34 33 30 29 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 2...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 101ms
memory: 4792kb

input:

1117
72
27 62 37 62 21 71 27 62 37 37 21 21 62 71 27 37 62 37 21 71 27 21 27 71 71 62 71 62 62 37 27 37 71 62 62 37 71 62 71 71 37 27 21 71 21 27 27 62 27 71 62 21 27 37 21 21 71 37 21 37 21 37 27 21 71 62 37 37 62 37 21 27
88
58 48 19 47 46 50 4 78 11 68 80 29 4 3 88 49 54 25 78 47 78 45 34 54 4 46...

output:

63 49 36 23 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
86 84 83 82 81 78 75 72 71 69 65 64 62 60 60 59 57 53 53 52 50 48 46 45 44 42 42 41 40 40 40 40 39 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38...

result:

ok 1117 lines