ABC F(*500)
ABC 364 F - Range Connect MST
Problem Statement
There is a graph with \(N + Q\) vertices, numbered \(1, 2, \ldots, N + Q\). Initially, the graph has no edges.
For this graph, perform the following operation for \(i = 1, 2, \ldots, Q\) in order:
- For each integer \(j\) satisfying \(L_i \leq j \leq R_i\), add an undirected edge with cost \(C_i\) between vertices \(N + i\) and \(j\).
Determine if the graph is connected after all operations are completed. If it is connected, find the cost of a minimum spanning tree of the graph.
A minimum spanning tree is a spanning tree with the smallest possible cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.
Constraints
- \(1 \leq N, Q \leq 2 \times 10^5\)
- \(1 \leq L_i \leq R_i \leq N\)
- \(1 \leq C_i \leq 10^9\)
- All input values are integers.
思路
首先容易想到按边权排序。我们默认每一次操作至少添加一次，那么我们可以将\(N+1\sim N+Q\)看成已经联通，我们可以初始状态看成\(N+1\)个连通块，目标是使最后只剩下一个联通块。而对于具体的一次操作我们显然需要连接范围内所有联通块。
利用set
注意到每一个连通块连接的点是连续的。我们用set储存每个连通块最小的点的编号，每次操作可以二分快速找到连通块数量。具体细节看代码。
struct node {
int l, r, c;
bool operator<(const node& u) const { return c < u.c; }
} a[N];
void solve() {
int n, q;
cin >> n >> q;
set<int> st;
for (int i = 1; i <= n; ++i) st.insert(i);
for (int i = 1; i <= q; ++i) cin >> a[i].l >> a[i].r >> a[i].c;
sort(a + 1, a + 1 + q);
ll ans = 0;
for (int i = 1; i <= q; ++i) {
auto s = st.upper_bound(a[i].l), e = st.upper_bound(a[i].r);
s--, e--;
ll cnt = 1;
if (s != e) {
s++;
while (s != e) {
auto it = ++s;
s--;
st.erase(s);
s = it;
cnt++;
}
cnt++;
st.erase(e);
}
ans += cnt * a[i].c;
}
if (st.size() > 1) ans = -1;
cout << ans;
}
利用并查集
原理和用set类似。
代码
struct node {
int l, r, c;
bool operator<(const node& u) const { return c < u.c; }
} a[N];
int pre[N];
inline int root(int x) { return pre[x] = (pre[x] == x ? x : root(pre[x])); }
void solve() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) pre[i] = i;
for (int i = 1; i <= q; ++i) cin >> a[i].l >> a[i].r >> a[i].c;
sort(a + 1, a + 1 + q);
ll ans = 0;
for (int i = 1; i <= q; ++i) {
auto [l, r, c] = a[i];
ans += c;
while (root(l) != root(r)) ans += c, pre[root(r)] = root(r) - 1;
}
if (root(1) != root(n)) ans = -1;
cout << ans;
}
利用线段树
我们维护一个数组\(t\)，若\(i\)与\(i+1\)联通，则为0否则为1。那么，\([l,r]\)的联通块数量为\([l,r)\)的和加1。证明很容易，不多赘述。
struct node {
int l, r, c;
bool operator<(const node& u) const { return c < u.c; }
} a[N];
#define ls p << 1
#define rs p << 1 | 1
struct tree {
ll l, r, s, lz, mlz;
} t[N << 2];
inline ll mo(ll x) { return (x + mod) % mod; }
inline void push_up(ll p) { t[p].s = mo(t[ls].s + t[rs].s); }
void update(ll p, ll k, ll x) {
t[p].s = mo(mo(t[p].s * k) + mo(x * (t[p].r - t[p].l + 1)));
t[p].mlz = mo(t[p].mlz * k);
t[p].lz = mo(mo(t[p].lz * k) + x);
}
void push_down(ll p) {
if (t[p].lz == 0 && t[p].mlz == 1) return;
update(ls, t[p].mlz, t[p].lz);
update(rs, t[p].mlz, t[p].lz);
t[p].lz = 0, t[p].mlz = 1;
}
void build(ll p, ll l, ll r) {
t[p] = {l, r, 0, 0, 1};
if (l == r) {
t[p].s = 1;
return;
}
ll mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(p);
}
void modify(ll p, ll l, ll r, ll k, ll x) {
if (l > r) return;
if (l <= t[p].l and r >= t[p].r) {
update(p, k, x);
return;
}
push_down(p);
if (l <= t[ls].r) modify(ls, l, r, k, x);
if (r >= t[rs].l) modify(rs, l, r, k, x);
push_up(p);
}
ll query(ll p, ll l, ll r) {
if (l > r) return 0;
if (l <= t[p].l and r >= t[p].r) return t[p].s;
push_down(p);
ll res = 0;
if (l <= t[ls].r) res = mo(res + query(ls, l, r));
if (r >= t[rs].l) res = mo(res + query(rs, l, r));
return res;
}
void solve() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= q; ++i) cin >> a[i].l >> a[i].r >> a[i].c;
sort(a + 1, a + 1 + q);
build(1, 1, n - 1);
ll ans = 0;
for (int i = 1; i <= q; ++i) {
auto [l, r, c] = a[i];
ans += c * (1 + query(1, l, r - 1));
modify(1, l, r - 1, 0, 0);
}
if (query(1, 1, n - 1)) ans = -1;
cout << ans;
}
ABC 361 F - x = a^b
Problem Statement
How many integers \(x\) between \(1\) and \(N\), inclusive, can be expressed as \(x = a^b\) using some positive integer \(a\) and a positive integer \(b\) not less than \(2\)?
Constraints
- All input values are integers.
- \(1 \le N \le 10^{18}\)
方法一
答案为
\[\sum_{i=1}^{n} [i可以被表示为a^b] \]注意到，一个数如果可以表示为\(a^{kb}\)那么它一定也可以被表示为\(a^b\)，那么我们可以先只考虑\(b\)为质数。我们先排除1，注意到\(2^{60}>10^{18}\)，那么我们可以只考虑\(60\)以内的质数，只有17个。设其为\(p_i\)，我们令\(A_i\)表示可以表示为\(a^{p_i}\)的个数。那么答案显然为
\[|A_1\cup A_2\cup \cdots\cup A_n| \]利用容斥原理显然可以解决。
但是由于精度问题，我们不能直接pow(n,1.0/x)解\(\sqrt[x]{n}\)，或者解出来后在向左右分别枚举一下，python是可以解决的。但是c++不行。
但是因为这几个质数乘积要小于\(60\)。实际需要解的数量是很少的，且\(x>2\)从1枚举也只需要\(1e6\)，因此可以直接枚举。而\(x=2\)时，也不能用sqrt(),得用sqrtl()。
int pri[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
int nr(ll n, ll r) {
if (r == 2) return sqrtl(n);
for (int i = 2;; ++i) {
if (pow(i, r) > n) {
return i - 1;
}
}
}
void solve() {
ll n;
cin >> n;
int up = 0;
for (; up < 17; ++up) {
if (1ll << pri[up] > n) break;
}
ll ans = 0;
for (int i = 1; i < (1ll << up); ++i) {
int cnt = 0, r = 1;
for (int j = 0; j < 17; ++j) {
if (i >> j & 1) cnt++, r *= pri[j];
if (r >= 60) break;
}
if (r < 60) {
ans += (cnt % 2 == 0 ? -1 : 1) * (nr(n, r) - 1);
}
}
cout << ans + 1;
}
方法二
不妨设\(f(x)\)为\(2\sim n\)仅可表示为\(a^x\)的个数，\(g(x)\)为可以表示为\(a^x\)的个数。
那么显然有
\[f(x)=g(x)-f(2x)-f(3x)\cdots \]从后向前递推即可。
到这里发现，前面的代码能过是运气好。因为pow还是会错。参考答案可以自己写个pow函数。
ll safe_pow(ll a, ll b) {
ll res = 1;
for (ll i = 0; i < b; i++) {
double dres = res;
dres *= a;
if (dres > 2e18) {
return 2e18;
}
res *= a;
}
return res;
}
int nr(ll n, ll r) {
if (r == 2) return sqrtl(n);
for (int i = 2;; ++i) {
if (safe_pow(i, r) > n) {
return i - 1;
}
}
}
int f[100], g[100];
void solve() {
ll n;
cin >> n;
ll ans = 1;
for (int i = 2; i <= 60; ++i) g[i] = nr(n, i) - 1;
for (int x = 60; x >= 2; --x) {
f[x] = g[x];
for (int k = 2; k * x <= 60; ++k) f[x] -= f[k * x];
ans += f[x];
}
cout << ans;
}
我们也可以用二分来替换开根运算，保证精度。但是懒得写