ABC F(500)

0d00 / 2024-08-28 / 原文

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;
}

我们也可以用二分来替换开根运算，保证精度。~~但是懒得写~~