Tricks

记录做题时的一些有趣 Tricks

\(\text{Prob.1}\) P3674 小清新人渣的本愿

奇奇妙妙角色关系图

算法：

莫队、\(\text{bitset}\)

思路

令 \(S=10^5\)

考虑使用 \(\text{bitset}\) 来 \(O(1)\) 维护当前区间出现的数

令 \(u,v\) 两个 \(\text{bitset}\) 分别维护 \(x,S-x\) 是否在区间中存在

第一个询问本质上是求区间中是否存在两个数 \(a,a+x\)，那么可以将 \(u\) 左移 \(x\) 位再和 \(u\) 按位与，如果结果存在 \(1\)，那么答案为真

第二个询问本质上是求区间中是否存在两个数 \(a,x-a\)，考虑将 \(v\) 右移 \(S-x\) 位，此时这个 \(\text{bitset}\) 的第 \(i\) 位维护的是 \(x-i\) 是否存在，和 \(u\) 按位与即可

第三个询问，由于 \(x \le S\)，可以暴力枚举 \(x\) 的因数，在 \(u\) 中判断是否存在即可

时间复杂度：\(O(n\sqrt{n}+\frac{n^2}{w})\)

Code

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5, kS = 1e5;

int n, m, a[kMaxN], op, l, r, x, B, c[kMaxN], cnt, L = 1, R;
bitset<kMaxN> u, v, ret;

struct Q {
  int id, op, l, r, x;
  bool operator<(const Q &o) const {
    return (l / B) != (o.l / B) ? (l / B) < (o.l / B) : (((l / B) & 1) ? r < o.r : r > o.r);
  }
} q[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m, B = sqrt(n);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> q[i].op >> q[i].l >> q[i].r >> q[i].x, q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  for (int i = 1; i <= m; i++) {
    for (; R < q[i].r; c[a[++R]]++, c[a[R]] == 1 && (u.set(a[R]), v.set(kS - a[R]), 0)) {
    }
    for (; L > q[i].l; c[a[--L]]++, c[a[L]] == 1 && (u.set(a[L]), v.set(kS - a[L]), 0)) {
    }
    for (; R > q[i].r; c[a[R]]--, c[a[R]] == 0 && (u.reset(a[R]), v.reset(kS - a[R]), 0), R--) {
    }
    for (; L < q[i].l; c[a[L]]--, c[a[L]] == 0 && (u.reset(a[L]), v.reset(kS - a[L]), 0), L++) {
    }
    if (q[i].op == 1) {
      ret[q[i].id] = (u & (u << q[i].x)).any();
    } else if (q[i].op == 2) {
      ret[q[i].id] = (u & (v >> (kS - q[i].x))).any();
    } else {
      for (int p = 1; p * p <= q[i].x; p++) {
        if (q[i].x % p == 0 && u[p] && u[q[i].x / p]) {
          ret[q[i].id] = 1;
          break;
        }
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << (ret[i] ? "hana" : "bi") << '\n';
  }
  return 0;
}

\(\text{Prob.2}\) ABC221G - Jumping sequence

算法

曼哈顿距离转切比雪夫距离，\(\text{bitset}\) 优化可行性 dp

思路

考虑将坐标系旋转 \(\frac{\pi}{4}\) 并拉长 \(\sqrt{2}\) 倍