# # AtCoder Beginner Contest 174 题解

## # Problem E - Logs

### # 题目描述

$N$根木条，每条长为$L_i$，最多锯$K$次，问锯完后最长的木条最短有多长（结果进位为整数）。

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n, k;
vector<int> a(n);
for (int i = 0; i < n; ++i)
ll l = 1, r = *max_element(a.begin(), a.end());
while (l <= r) {
ll mid = l + (r - l) / 2;
ll req = 0;
for (int i : a)
req += (i - 1) / mid;
if (req > k)
l = mid + 1;
else
r = mid - 1;
}
printf("%lld", l);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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

## # Problem F - Range Set Query

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

template <class T> class FenwickTree {
int limit;
vector<T> arr;

T lowbit(T x) { return x & (-x); }

public:
FenwickTree(int limit) {
this->limit = limit;
arr = vector<T>(limit + 1);
}

void update(int idx, T delta) {
for (; idx <= limit; idx += lowbit(idx))
arr[idx] += delta;
}

T query(int idx) {
T ans = 0;
for (; idx > 0; idx -= lowbit(idx))
ans += arr[idx];
return ans;
}
};

class Solution {
public:
void solve() {
int n, q;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
vector<pair<int, int>> queries;
for (int i = 0; i < q; ++i) {
int l, r;
queries.emplace_back(l, r);
}
vector<int> order(q);
for (int i = 0; i < q; ++i)
order[i] = i;
sort(order.begin(), order.end(),
[&](int i, int j) { return queries[i].second < queries[j].second; });
vector<int> ans(q);
vector<int> pos(n + 1);
int last = 0;
FenwickTree<int> ft(n);
for (int i = 0; i < q; ++i) {
int k = order[i];
int l = queries[k].first, r = queries[k].second;
for (int j = last + 1; j <= r; ++j) {
if (pos[a[j]] != 0)
ft.update(pos[a[j]], -1);
ft.update(j, 1);
pos[a[j]] = j;
}
ans[k] = ft.query(r) - ft.query(l - 1);
last = r;
}
for (int i : ans)
printf("%d\n", i);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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