14th Chongqing CPC
Table of Contents
F. 修修改
First, since all element can only be increased, thus, there should be \(\ge i\) elements that are \(\le i\). Since the given sequence is non-decreasing, it can be inferred that \(a_{i} \le i\) is the necessity and sufficiency for the problem to be solvable.
Then, let’s develop the strategy. The condition \(a_{1}=1\) always holds. Suppose \(a_{i}=i\) and \(a_{1:i}\) is already a permutation of \(1\sim i\), and let’s inspect \(a_{i+1}\). If \(a_{i+1}=i+1\) then ignore it. If not, this implies that \(a_{i+1}=i\). Let’s find an \(r\) such that it is the first element to \(l\)’s right and \(a_{r}=r\) (or \(n+1\) if not found).
Now, we can prove that we can transform the sequence \([l,r]\) into \(r-1, l, l+1, \dots, r-2, r\).
K. 街树的影子
Suppose we know the answer of \( i+1 \sim n \)-th tree, consider how to add \( i \)-th tree.
Since we know for sure that \(i\)-th tree must be on the left hand side of \(i+1\)-th tree, the delta area must be a trapezoid (or a triangle) that may fully cover some small triangles.
Suppose the current tree to add is \(x\)-th triangle positioning at \(x\) with height \(d_{x}\). To find the other side of the trapezoid (as well as the height), we should look for the smallest \(y\) such that
\[ x\lt y\le x+d_{x}\le y+d_{y} \]
Then, the answer can be updated with
\[ A_{x} = \begin{cases} A_{y} + (2d_{x}-y+x)(y-x) & \text{if \(x\) cannot cover all suffix triangles} \\ d_{x}^{2} & \text{if \(x\) covers all suffix triangles} \end{cases} \]
To support such operations, we can use segment tree by storing \(i+d_{i}\) at position \(i\) and maintain range maximum. We query on range \( [x+1, x+d_{x}] \) for \(y\), and recurse left-then-right with \( maxv \ge x+d_{x} \) check to find the smallest \( y \).
Insertion and single-side recursion can be done in \( O(\log n) \), therefore, the solution is \( O(n\log n) \).
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using i64 = long long;
constexpr i64 MAXV = 1e18;
struct tree {
std::vector<i64> t;
int n;
private:
void pullup(int p) { t[p] = std::max(t[p << 1], t[p << 1 | 1]); }
void insert(int pos, i64 v, int p, int l, int r) {
if (l == r)
return void(t[p] = v);
int mid = l + ((r - l) >> 1);
pos <= mid ? insert(pos, v, p << 1, l, mid)
: insert(pos, v, p << 1 | 1, mid + 1, r);
pullup(p);
}
auto query(int L, int R, i64 val, int p, int l, int r) -> int {
if (r < L or l > R or t[p] < val)
return -1;
if (l == r)
return l;
int mid = l + ((r - l) >> 1);
if (R <= mid)
return query(L, R, val, p << 1, l, mid);
else if (L > mid)
return query(L, R, val, p << 1 | 1, mid + 1, r);
else {
if (t[p << 1] >= val)
return query(L, R, val, p << 1, l, mid);
else if (t[p << 1 | 1] >= val)
return query(L, R, val, p << 1 | 1, mid + 1, r);
else
return -1;
}
}
public:
tree(int size) : t(size * 4, 0), n(size) {}
void insert(int pos, i64 v) { insert(pos, v, 1, 0, n - 1); }
int query(int l, i64 val) {
int r = std::min(i64(n - 1), val);
int ans = query(l, r, val, 1, 0, n - 1);
return ans == -1 ? n : ans;
}
};
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
int n;
std::cin >> n;
std::vector<i64> d(n);
for (int i = 0; i < n; i++)
std::cin >> d[i];
std::vector<i64> A(n + 1, 0);
tree T(n);
A[n - 1] = d[n - 1] * d[n - 1];
T.insert(n - 1, n - 1 + d[n - 1]);
for (int i = n - 2; i >= 0; i--) {
int y = T.query(i + 1, i + d[i]);
if (y == n)
A[i] = d[i] * d[i];
else
A[i] = A[y] + (d[i] + d[i] - y + i) * (y - i);
T.insert(i, i + d[i]);
}
for (int i = 0; i < n; i++)
std::cout << A[i] << "\n";
}
L. 样品检测
Represent all indexes in binary, and find out all bit differences between the good and the bad in \(2\log n\) queries. Then, find out the common bits in at most \(\log n-1\) queries.
M. Lowbit OR Lowbit
The following lemmas are useful. Let \( \ell(x)=\texttt{lowbit}(x) \), and \( x\oplus y=x\texttt{ bitor }y \)
Lemma of the Transitivity.
\( \ell(x \oplus y) = \min\left( \ell(x), \ell(y) \right) \)
Therefore, we can derive a greedy solution. Sort all \(x\)-s by \( \ell(x) \). Then we first merge \( x_{i},x_{j} \) that have same lowbit. Then we merge \( x_{i},x_{j} \) from smallest to largest.
The overall time complexity is on sorting, giving a \( O(n\log n) \) solution.
#include <algorithm>
#include <iostream>
#include <vector>
int lowbit(int x) { return x & -x; }
void work() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &x : a)
std::cin >> x, x = lowbit(x);
std::sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < n;) {
int j = i;
while (j < n && a[j] == a[i])
j++;
ans += 1ll * a[i] * (j - i - 1);
i = j;
}
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 1; i < a.size(); i++)
ans += 1ll * (a[i] | a[0]);
std::cout << ans << "\n";
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while (t--)
work();
}