2019-9-14

未分类

bales

在以下几种情况会出现不合法：1.多个最小值相同的区间无交集或交集不唯一，因为没有重复的数字。2.在几个最小值较大区间的并集中出现了一个最小值较小的子区间，很显然不行。二分答案第一个出现矛盾的位置，将其及其前面的区间按最小值降序排序，然后用一颗支持区间覆盖操作的线段树来维护错误情况 2。

#include <iostream>
#include <cstdio>
#include <algorithm>
const int MAXN = 1e6;
const int MAXQ = 25000;
int n, Q;
struct Range {
  int l, r, val;
  Range() : l(0), r(0), val(0) {}
  friend bool operator< (const Range &lhs, const Range &rhs) {
    return lhs.val > rhs.val;
  }
} a[MAXQ | 1], b[MAXQ | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
namespace SegTree {
  struct Node {
    int sumv, lazy;
    Node *ch[2];
    Node() : sumv(0), lazy(0) {
      ch[0] = ch[1] = NULL;
    }
  } *root;
  void push_down(Node *o, int l, int r) {
    if (o -> lazy) {
      int mid = (l + r) >> 1;
      o -> ch[0] -> sumv = (mid - l + 1);
      o -> ch[0] -> lazy = 1;
      o -> ch[1] -> sumv = (r - mid);
      o -> ch[1] -> lazy = 1;
      o -> lazy = 0;
    }
  }
  void push_up(Node *o) {
    o -> sumv = o -> ch[0] -> sumv + o -> ch[1] -> sumv;
  }
  void build(Node *&o, int l, int r) {
    if (o == NULL) o = new Node;
    else o -> sumv = o -> lazy = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(o -> ch[0], l, mid);
    build(o -> ch[1], mid + 1, r);
  }
  void modify(Node *&o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      o -> sumv = (r - l + 1);
      o -> lazy = 1;
      return;
    }
    push_down(o, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(o -> ch[0], l, mid, ql, qr);
    if (mid < qr) modify(o -> ch[1], mid + 1, r, ql, qr);
    push_up(o);
  }
  int query(Node *&o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return o -> sumv;
    push_down(o, l, r);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res = query(o -> ch[0], l, mid, ql, qr);
    if (mid < qr) res += query(o -> ch[1], mid + 1, r, ql, qr);
    return res;
  }
}
using namespace SegTree;
bool check(int lim) {
  build(root, 1, n);
  for (int i = 1; i <= lim; ++i) b[i] = a[i];
  std::sort(b + 1, b + 1 + lim);
  for (int i = 1, j; i <= lim; i = j) {
    for (j = i; j <= lim && b[j].val == b[i].val; ++j);
    int l1 = b[i].l, l2 = b[i].l, r1 = b[i].r, r2 = b[i].r;
    for (int k = i + 1; k < j; ++k) {
      l1 = std::min(l1, b[k].l);
      r1 = std::max(r1, b[k].r);
      l2 = std::max(l2, b[k].l);
      r2 = std::min(r2, b[k].r);
    }
    if (l2 > r2) return false;
    if (query(root, 1, n, l2, r2) == (r2 - l2 + 1)) return false;
    modify(root, 1, n, l1, r1);
  }
  return true;
}
int main() {
  n = read();
  Q = read();
  for (int i = 1; i <= Q; ++i) {
    a[i].l = read();
    a[i].r = read();
    a[i].val = read();
  }
  int l = 1, r = Q, mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (!check(mid)) {
      r = mid - 1;
      ans = mid;
    } else l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}

saber

每条不合法的路径都可以与一条从点 $(-2,2)$ 出发的路径相对应，那么用总方案数减去不合法的方案数即 $C_{n+m}^{m}-C_{n+m}^{m-2}$，使用卢卡斯定理计算。

good

考虑答案其实就是求 $\sum\limits_{i=1}^n C_{d(i)}^2$，使用线性筛计算 $d(i)$。
细节：对于每个数计算其最小质因子出现的次数（记为 cnt），在线性筛的时候如果 $prime[j]|i$，则 $cnt[i * prime[j]]=cnt[i] + 1$，$d[i * prime[j]]=\frac{d[i]*cnt[i]+2}{cnt(i)+1}$，否则 $cnt[i * prime[j]]=1$，$d[i * prime[j]]=d[i]*2$。

#include <iostream>
#include <cstdio>
const int MAXN = 1e7;
const int MOD = 998244353;
int n, tot;
int minSum[MAXN | 1], ans[MAXN | 1], prime[MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int main() {
  n = read();
  int res = 0;
  for (int i = 2; i <= n; ++i) {
    if (ans[i] == 0) prime[++tot] = i, ans[i] = 2, minSum[i] = 1;
    for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
      if (i % prime[j] == 0) {
        minSum[i * prime[j]] = minSum[i] + 1;
        ans[i * prime[j]] = ans[i] * (minSum[i] + 2) / (minSum[i] + 1);
        break;
      } else {
        minSum[i * prime[j]] = 1;
        ans[i * prime[j]] = ans[i] * 2;
      }
    }
    res += (1LL * (ans[i] * (ans[i] - 1)) / 2) % MOD;
    res %= MOD;
  }
  printf("%d\n", res);
}

rich

太神仙了，不改了