2021牛客多校2
总览
| 题号 | 标题 | 团队的状态 |
|---|---|---|
| A | Arithmetic Progression | 通过 |
| B | Cannon | 通过 |
| C | Draw Grids | 通过 |
| D | Er Ba Game | 通过 |
| E | Gas Station | 通过 |
| F | Girlfriend | 通过 |
| G | League of Legends | 通过 |
| H | Olefin | 未通过 |
| I | Penguins | 通过 |
| J | Product of GCDs | 通过 |
| K | Stack | 通过 |
| L | WeChat Walk | 通过 |
Arithmetic Progression
给定每个元素互不相同的序列 \(a_n\)，求排序后能构成等差数列的区间个数。
\(1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9\)
结论：对于元素互不相同的序列 \(b_n\)，其排序后是公差为 \(d\) 等差数列的充要条件是 \(d=\gcd(|b_2-b_1|,|b_3-b_2|,\dots)\) 且 \(\max b_i - \min b_i = (n-1)d\)。
证明：
必要性：
设 \(b_i = k_id + b_1\) 且 \(b_n\) 排序后为等差数列，则 \(k_i\) 是 \(0, 1, \dots n-1\) 的一个排列，所以 \(\max b_i - \min b_i= (n-1)d\)。
根据辗转相减法：
\(\gcd(|b_2-b_1|,|b_3-b_2|,\dots)\ = \gcd(|b_2-b_1|, |b_3 - b_1|, \dots) = \gcd(d, 2d, \dots) = d\)。
充分性：
不妨设 \(b_1 < b_2 <\dots < b_n\)，\(\gcd(|b_2-b_1|,|b_3-b_2|,\dots)\ = \gcd(|b_2-b_1|, |b_3 - b_1|, \dots) = d = \frac{b_n - b_1}{n-1}\)。
设 \(b_i = k_id + b_1\)，则 \(k_1 = 0 < k_2 \dots < k_n = n - 1\)，所以 \(k_i = i - 1,b_i = (i-1)d+b_1\)，为等差数列。
于是问题转化为求 \(\max a_i - \min a_i = (r-l)\gcd(|a_{l+1}-a_l|, |a_{l+2} - a_{l+1}|, \dots)\) 的区间个数。
由上面的证明不难发现 \(\max a_i - \min a_i - (r-l)\gcd(|a_{l+1}-a_l|, |a_{l+2} - a_{l+1}|, \dots) \geq 0\)，所以用线段树维护这个值的最小值以及最小值的个数。
每次移动右端点时，极差只需修改一个区间，但每个点的 \(\gcd\) 都可能被修改。
考虑一个点作为左端点的区间 \(\gcd\) 被修改的次数，发现每次修改至少会折半，所以最多修改 \(\log\) 次，于是在线段树上暴力修改即可。
不需要 zkw 跑得也很快！
// Author: HolyK
// Created: Wed Jul 21 12:59:35 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
int n, a[N];
#define ls o << 1
#define rs o << 1 | 1
LL min[N << 2], tag[N << 2];
int cnt[N << 2], gcd[N << 2];
void pushup(int o) {
min[o] = std::min(min[ls], min[rs]);
cnt[o] = (min[ls] == min[o] ? cnt[ls] : 0) + (min[rs] == min[o] ? cnt[rs] : 0);
min[o] += tag[o];
gcd[o] = gcd[ls] == gcd[rs] ? gcd[ls] : -1;
}
void update(int o, int l, int r, int x, int y, int z) {
if (gcd[o] > 0 && z % gcd[o] == 0) {
min[o] -= gcd[o];
tag[o] -= gcd[o];
return;
}
if (l == r) {
int t = gcd[o];
gcd[o] = std::gcd(gcd[o], z);
min[o] -= LL(gcd[o] - t) * (y - l) + gcd[o];
cnt[o] = 1;
return;
}
int m = l + r >> 1;
if (x <= m) update(ls, l, m, x, y, z);
if (y > m) update(rs, m + 1, r, x, y, z);
pushup(o);
}
void add(int o, int l, int r, int x, int y, int z) {
if (x <= l && r <= y) {
min[o] += z;
tag[o] += z;
return;
}
int m = l + r >> 1;
if (x <= m) add(ls, l, m, x, y, z);
if (y > m) add(rs, m + 1, r, x, y, z);
pushup(o);
}
int ask(int o, int l, int r, int x, int y, int z) {
if (y < l || r < x) return 0;
if (x <= l && r <= y) return min[o] + z == 0 ? cnt[o] : 0;
int m = l + r >> 1;
z += tag[o];
return ask(ls, l, m, x, y, z) + ask(rs, m + 1, r, x, y, z);
}
int s1[N], s2[N], t1, t2; // min, max
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
std::cin >> n;
memset(min, 0, n + 1 << 5);
memset(tag, 0, n + 1 << 5);
memset(cnt, 0, n + 1 << 4);
memset(gcd, 0, n + 1 << 4);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
LL ans = n;
t1 = t2 = s1[1] = s2[1] = 1;
for (int i = 2; i <= n; i++) {
while (t1 && a[s1[t1]] > a[i]) {
add(1, 1, n, s1[t1 - 1] + 1, s1[t1], a[s1[t1]]);
t1--;
}
while (t2 && a[s2[t2]] < a[i]) {
add(1, 1, n, s2[t2 - 1] + 1, s2[t2], -a[s2[t2]]);
t2--;
}
add(1, 1, n, s1[t1] + 1, i, -a[i]);
add(1, 1, n, s2[t2] + 1, i, a[i]);
s1[++t1] = s2[++t2] = i;
update(1, 1, n, 1, i - 1, a[i] - a[i - 1]);
ans += ask(1, 1, n, 1, i - 1, 0);
}
std::cout << ans << "\n";
}
return 0;
}Cannon
有一个 \(2×10^{100}\) 的棋盘，第一行摆了 \(a\) 个炮，第二行摆了 \(b\) 个炮。
依次求发生 \(0, 1, 2, \dots, a + b - 2\) 个炮吃炮事件的方案数。
有考虑两行之间的顺序和不考虑两行之间的顺序 两个子问题。
\(1 \leq a, b \leq 5 \times 10^6\)
一行 \(n\) 个炮操作 \(m\) 次的方案是 \(2^m \dfrac{(n - 2)!}{(n - 2 - m)!}\)。
设 \(n = a - 2, m = b - 2\)，问题即求 \[ \begin{aligned} ans_1 &= 2^k \sum_{i = 0}^k \binom{k}{i}\frac{n!}{(n - i)!}\frac{m!}{(m - k + i)!}\\ &= 2^k k!\sum_{i = 0}^k \frac{n!}{(n - i)!i!}\frac{m!}{(m - k + i)!(k-i)!}\\ &= 2^k k!\sum_{i = 0}^k \binom{n}{i}\binom{m}{k-i}\\ &= 2^k k!\binom{n+m}{k}\\ ans_2 &= 2^k \sum_{i = 0}^k \frac{n!}{(n - i)!}\frac{m!}{(m - k + i)!}\\ &= 2^k \frac{n!m!}{(n + m - k)!}\sum_{i = 0}^k \frac{(n+m-k)!}{(n-i)!(m-k+i)!}\\ &= 2^k \frac{n!m!}{(n + m - k)!}\sum_{i = 0}^k \binom{n+m-k}{n-i}\\ &= 2^k \frac{n!m!}{(n + m - k)!}\sum_{i = n}^{n-k} \binom{n+m-k}{i} \end{aligned} \]
问题一直接递推，问题二维护一个组合数前缀和即可。
// Author: HolyK
// Created: Tue Jul 20 21:51:46 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(1e9 + 9);
inline void inc(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
int fpow(int x, int k = P - 2) {
int r = 1;
for (; k; k >>= 1, x = 1LL * x * x % P) {
if (k & 1) r = 1LL * r * x % P;
}
return r;
}
constexpr int N(1e7 + 5);
int n, m, fac[N], ifac[N];
int bin(int n, int m) {
return m >= 0 && m <= n ? 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P : 0;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
n -= 2, m -= 2;
fac[0] = ifac[0] = 1;
int k = n + m;
for (int i = 1; i <= k; i++) fac[i] = 1LL * fac[i - 1] * i % P;
ifac[k] = fpow(fac[k]);
for (int i = k - 1; i; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
int ans = 1;
for (int i = 1, x = 1; i <= k; i++) {
x = 2LL * x * (k - i + 1) % P;
ans ^= x;
}
std::cout << ans << " ";
ans = 1;
int s1 = 0, s2;
for (int i = 0; i < n; i++) inc(s1, bin(k, i));
inc(s2 = s1, bin(k, n));
for (int i = 1, x = fpow(bin(k, n)); i <= k; i++) {
s1 = (s1 - bin(k - i, n - i) + P) * (P + 1LL >> 1) % P;
s2 = (s2 + bin(k - i, n)) * (P + 1LL >> 1) % P;
x = 2LL * x * (k - i + 1) % P;
ans ^= 1LL * x * (s2 - s1 + P) % P;
}
std::cout << ans << "\n";
return 0;
}Draw Grids
队友切了。
Er Ba Game
签到题。
Gas Station
给定一棵树，点权 \(a_i\)，边权 \(w_i\)，经过一个点能量加 \(a_i\)，经过一条边能量减 \(w_i\)，\(q\) 次询问从点 \(x_i\) 出发初始能量为 \(d_i\) 中间能量不小于 0 且不能经过点 \(p_i\)，沿着最短路径能到达的点数。
\(1 \leq n,q \leq 10^5, 1 \leq a_i, w_i \leq 10^9, 0 \leq d_i \leq 10^{14}\)
离线，然后是点分治基础题。
// Author: HolyK
// Created: Wed Jul 21 14:21:43 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
int n, m, a[N], ans[N];
std::vector<PII> g[N];
std::vector<std::tuple<LL, int, int>> q[N];
bool vis[N];
int root, tSize, mSize, siz[N];
void getSize(int x, int fa) {
siz[x] = 1 + q[x].size();
for (auto [y, z] : g[x]) {
if (y == fa || vis[y]) continue;
getSize(y, x);
siz[x] += siz[y];
}
}
void getRoot(int x, int fa) {
int max = tSize - siz[x];
for (auto [y, z] : g[x]) {
if (y == fa || vis[y]) continue;
getRoot(y, x);
smax(max, siz[y]);
}
if (smin(mSize, max)) root = x;
}
LL up[N], dn[N], sum[N];
int in[N], out[N], id[N], cnt;
void pre(int x, int fa) {
in[x] = ++cnt;
id[cnt] = x;
for (auto [y, z] : g[x]) {
if (y == fa || vis[y]) continue;
up[y] = std::max(0LL, up[x] + z - a[y]);
dn[y] = std::max(dn[x], z - sum[x]);
sum[y] = sum[x] + a[y] - z;
pre(y, x);
}
out[x] = cnt;
}
struct Qry {
LL d;
int l, r, p, id;
bool operator<(const Qry &rhs) const {
return d < rhs.d;
}
} s[N];
int tot, p[N], c[N];
void add(int p, int x) {
for (; p <= cnt; p += p & -p) c[p] += x;
}
int ask(int p) {
int r = 0;
for (; p; p -= p & -p) r += c[p];
return r;
}
void solve(int x) {
getSize(x, 0), mSize = tSize = siz[x], getRoot(x, 0), x = root;
// std::cerr << "solve! " << x << "\n";
cnt = tot = 0;
up[x] = dn[x] = 0;
sum[x] = a[x];
pre(x, 0);
vis[x] = true;
for (auto [d, p, id] : q[x]) {
if (p == x) continue;
int l = 0, r = 0;
if (in[p]) l = in[p], r = out[p];
s[++tot] = {d, l, r, 0, id};
}
for (auto [y, z] : g[x]) {
if (vis[y]) continue;
for (int i = in[y]; i <= out[y]; i++) {
int x = id[i];
// std::cerr << "! " << x << " " << root << " " << up[x] << " " << dn[x] << "\n";
for (auto [d, p, id] : q[x]) {
if (d < up[x] || in[p] <= in[x] && out[x] <= out[p]) continue;
int l = 0, r = 0;
if (in[p] && !(in[y] <= in[p] && out[p] <= out[y])) l = in[p], r = out[p];
s[++tot] = {d + sum[x] - a[root], l, r, y, id};
}
}
}
std::sort(s + 1, s + 1 + tot);
for (int i = 1; i <= cnt; i++) p[i] = id[i];
std::sort(p + 1, p + 1 + cnt, [&](int i, int j) {
return dn[i] < dn[j];
});
for (int i = 1; i <= cnt; i++) c[i] = 0;
for (int i = 1, j = 1; i <= tot; i++) {
for (; j <= cnt && dn[p[j]] <= s[i].d; j++) {
add(in[p[j]], 1);
}
ans[s[i].id] += j - 1;
if (s[i].l) ans[s[i].id] -= ask(s[i].r) - ask(s[i].l - 1);
if (s[i].p) ans[s[i].id] -= ask(out[s[i].p]) - ask(in[s[i].p] - 1);
// std::cerr << "!! " << ans[s[i].id] << "\n";
}
for (int i = 1; i <= cnt; i++) {
in[id[i]] = out[id[i]] = 0;
}
for (auto [y, z] : g[x]) {
if (vis[y]) continue;
solve(y);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for (int i = 1, x, y, z; i < n; i++) {
std::cin >> x >> y >> z;
g[x].push_back({y, z});
g[y].push_back({x, z});
}
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for (int i = 1, x, p; i <= m; i++) {
LL d;
std::cin >> x >> d >> p;
q[x].push_back({d, p, i});
}
solve(1);
for (int i = 1; i <= m; i++) {
std::cout << ans[i] << "\n";
}
return 0;
}Girlfriend
求球的体积交。
我不会积分，我是傻逼，就这高数还考99。
#include <bits/stdc++.h>
using DB = double;
#define double long double
struct P {
double x, y, z;
P operator+(P r) const {
return {x + r.x, y + r.y, z + r.z};
}
P operator-(P r) const {
return {x - r.x, y - r.y, z - r.z};
}
P operator*(double r) const {
return {r * x, r * y, r * z};
}
P operator/(double r) const {
return {x / r, y / r, z / r};
}
double dist2() const {
return x * x + y * y + z * z;
}
double dist() const {
return sqrt(dist2());
}
} a[4];
void get(P a, P b, double k, P &c, double &r) {
auto u = (b * k - a) / (k - 1), v = (b * k + a) / (k + 1);
c = (u + v) / 2;
r = (u - v).dist() / 2;
}
constexpr double EPS(1e-10);
const double PI(acos((double)-1.0));
double sqr(double r) { return r * r; }
double cal(double r) { return r * sqrt(r); }
int main() {
int t;
scanf("%d", &t);
while (t--) {
for (auto &[x, y, z] : a) {
DB a, b, c;
scanf("%lf%lf%lf", &a, &b, &c);
x = a, y = b, z = c;
}
int k1, k2;
scanf("%d%d", &k1, &k2);
P c1, c2;
double r1, r2;
get(a[0], a[1], k1, c1, r1);
get(a[2], a[3], k2, c2, r2);
double d = (c1 - c2).dist();
if (d >= r1 + r2) {
puts("0");
continue;
}
if (r1 < r2) std::swap(r1, r2);
if (d <= r1 - r2) {
printf("%.10f\n", DB(4.0 / 3 * PI * r2 * r2 * r2));
continue;
}
// printf("%f %f %f\n", r1, r2, d);
double z = (r1 * r1 - r2 * r2 + d * d) / (2 * d), ans;
if (z < d) {
z = r1 * r1 - z * z;
ans = 2.0 / 3 * (r1 * r1 * r1 + r2 * r2 * r2 - cal(r1 * r1 - z) - cal(r2 * r2 - z)) - d * z;
} else {
z = r1 * r1 - z * z;
ans = 2.0 / 3 * (-r1 * r1 * r1 + r2 * r2 * r2 + cal(r1 * r1 - z) - cal(r2 * r2 - z)) + d * z;
ans = 4.0 / 3 * r2 * r2 * r2 - ans;
}
ans *= PI;
printf("%.10f\n", DB(ans));
}
return 0;
}League of Legends
\(n\) 个区间 \([l_i, r_i)\) 划分成 \(k\) 个集合，要求每个集合的区间交不为空， 求 \(\sum r - l\) 最大值。
\(1 \leq k \leq n \leq 5000\)
如果一个区间包含了另一个小区间，那么这个区间要么单独成一个集合，要么和这个小区间在一个集合。
看出这个之后就好做了。
把大区间都拿走后，剩下的就是不存在包含关系的小区间，按左端点排序后，显然选连续的一段更优，于是可以DP，最后再算上大区间的贡献。
由于没有包含关系，右端点也是递增的，可以用单调队列优化成 \(O(nk)\)。
// Author: HolyK
// Created: Mon Jul 19 19:26:36 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
#define int LL
using PII = std::pair<int, int>;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
std::vector<PII> a(n), b;
std::vector<int> c;
for (int i = 0; i < n; i++) {
std::cin >> a[i].first >> a[i].second;
}
std::sort(a.begin(), a.end());
b.push_back(a.back());
for (int i = n - 2, m = a.back().second; i >= 0; i--) {
if (a[i].second >= m) {
c.push_back(a[i].second - a[i].first);
} else {
b.push_back(a[i]);
m = a[i].second;
}
}
std::reverse(b.begin(), b.end());
std::vector f(k + 1, std::vector<int>(n = b.size(), -1e18));
for (int i = 0; i < n; i++) {
if (b[0].second > b[i].first) {
f[1][i] = b[0].second - b[i].first;
}
}
// std::cerr << f[1].back() << " ";
for (int i = 2; i <= k && i <= n; i++) {
std::vector<PII> q;
int s = 0;
for (int j = i - 1; j < n; j++) {
while (s < q.size() && q[s].second <= b[j].first) s++;
PII v = {b[j].second + f[i - 1][j - 1], b[j].second};
while (s < q.size() && q.back() <= v) q.pop_back();
q.push_back(v);
f[i][j] = q[s].first - b[j].first;
}
}
// std::cerr << "!! " << n << "\n";
int ans = f[k].back();
std::sort(c.rbegin(), c.rend());
for (int i = 0, s = 0; i < c.size() && i < k; i++) {
s += c[i];
smax(ans, s + f[k - i - 1].back());
}
smax(ans, 0);
std::cout << ans << "\n";
return 0;
}Olefin
Penguins
队友切了。
Product of GCDs
给定 \(n\) 个数 \(x_1, x_2, \dots, x_n\)，从中选出 \(k\) 个数求 \(\gcd\)，求所有方案 \(\gcd\) 之积，答案 \(\bmod P\)。
\(T \leq 60, n \leq 4 \times 10^4, 1 \leq x_i \leq 8 \times 10^4, k \leq 30, 10^6 \leq P \leq 10^{14}\)。
枚举 \(\gcd\) 的质因子和指数，用组合数计算贡献。
\(P\) 不是质数，但 \(k\) 只有30，可以递推求组合数。
指数贡献需要欧拉降幂，由于 \(P \geq 10^6 > 8 \times 10^4\)，不需要用到拓展欧拉定理。
求 \(\varphi(P)\) 要筛素数或者直接 Pollard-rho。
// Author: HolyK
// Created: Mon Jul 19 21:21:30 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
#define gcd __gcd
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
using LLL = __int128_t;
LL fpow(LL x, LL k, LL p) {
LL r = 1;
for (; k; k >>= 1, x = (LLL)x * x % p) {
if (k & 1) r = (LLL)r * x % p;
}
return r;
}
bool isPrime(LL p) {
if (p < 2) return false;
if (p == 2 || p == 3) return true;
LL d = p - 1, r = 0;
static std::mt19937 rnd(19260817);
for (; d & 1 ^ 1; d >>= 1) r++;
for (LL k = 0; k < 10; k++) {
LL a = rnd() % (p - 2) + 2, x = fpow(a, d, p);
if (x == 1 || x == p - 1) continue;
for (int i = 0; i < r - 1 && x != p - 1; i++) {
x = (LLL)x * x % p;
}
if (x != p - 1) return false;
}
return true;
}
LL pr(LL n) {
auto f = [&](LL x) { return (LLL)x * x % n + 1; };
LL p = 2, q;
for (LL i = 1, x = 0, y = 0, t = 30; t++ % 40 || std::gcd(p, n) == 1; x = f(x), y = f(f(y))) {
if (x == y) x = ++i, y = f(x);
q = (LLL)p * (x - y > 0 ? x - y : y - x) % n;
if (q) p = q;
}
return std::gcd(p, n);
}
std::vector<LL> factor(LL n) {
if (n == 1) return {};
if (isPrime(n)) return {n};
LL x = pr(n);
auto l = factor(x), r = factor(n / x);
l.insert(l.end(), r.begin(), r.end());
return l;
}
std::vector<int> primes;
bool np[80004];
void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!np[i]) primes.push_back(i);
for (int j : primes) {
if (1LL * i * j > n) break;
np[i * j] = true;
if (i % j == 0) break;
}
}
}
LL getPhi(LL x) {
auto v = factor(x);
for (auto u : v) x -= x / u;
return x;
// LL r = x;
// for (int i : primes) {
// if (i > x / i) break;
// if (x % i) continue;
// do x /= i; while (x % i == 0);
// r -= r / i;
// }
// if (x > 1) r -= r / x;
// return r;
}
LL bin[40004][33];
int cnt[80005];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
sieve(8e4);
// sieve(1e7);
int t, n, k;
LL p, phi;
std::cin >> t;
while (t--) {
std::cin >> n >> k >> p;
phi = getPhi(p);
for (int i = 0; i <= n; i++) {
bin[i][0] = 1;
for (int j = 1; j <= i && j <= k; j++) {
bin[i][j] = bin[i - 1][j] + bin[i - 1][j - 1];
if (bin[i][j] >= phi) bin[i][j] -= phi;
}
}
memset(cnt, 0, sizeof cnt);
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
cnt[x]++;
}
LL ans = 1;
for (int x : primes) {
LL sum = 0;
for (LL y = x; y <= 8e4; y *= x) {
int c = 0;
for (int k = y; k <= 8e4; k += y) c += cnt[k];
sum += bin[c][k];
if (sum >= p) sum -= phi;
}
if (sum) {
ans = (LLL)ans * fpow(x, sum, p) % p;
}
}
std::cout << ans << "\n";
}
return 0;
}Stack
排列 \(a_i\) 求单调栈时 \(b_i\) 为插入 \(a_i\) 后单调栈的大小。给出 \(b_i\) 的一些位置的值，还原一个合法的 \(a_i\)。
\(n \leq 10^5\)
队友给了一个构造方法，倒着枚举 \(b_i\)，每次取剩余数中最小的 \(b_i\) 个从大往小填，遇到不为零的 \(b_j\) 为止。
直接维护是 \(O(n^2)\) 的，我拿树状数组维护这个过程，复杂度 \(O(n \log n)\)。
标解是拓扑或者链表，还没写，好像是洛谷原题。
#include <bits/stdc++.h>
std::vector<int> solve(std::vector<int> a) {
int n = a.size();
std::vector<int> b, c;
for (int i = 0; i < a.size(); i++) {
while (!b.empty() && b.back() > a[i]) b.pop_back();
b.push_back(a[i]);
c.push_back(b.size());
}
return c;
}
constexpr int N(1e6 + 5);
int n, a[N], b[N], c[N], s[N];
void add(int p, int x) {
for (; p <= n; p += p & -p) c[p] += x;
}
int ask(int p) {
int r = 0;
for (; p; p -= p & -p) r += c[p];
return r;
}
int get(int x) {
int p = 0;
for (int k = 1 << std::__lg(n); k; k >>= 1) {
if (p + k <= n && c[p + k] + k < x) {
x -= c[p += k] + k;
}
}
return p + 1;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int k;
std::cin >> n >> k;
while (k--) {
int x, y;
std::cin >> x >> y;
b[x] = y;
if (y > x) {
return puts("-1"), 0;
}
}
std::vector<int> tmp(b + 1, b + 1 + n);
int tot = n;
for (int i = n; i; i--) {
if (!b[i]) continue;
if (tot < b[i]) {
return puts("-1"), 0;
}
int x = b[i];
b[i] = 0;
for (int j = i; j && !b[j] && x; j--) {
a[j] = get(x--);
add(a[j], -1);
tot--;
}
}
for (int i = n; i; i--) {
if (!a[i]) {
if (tot < 1) {
return puts("-1"), 0;
}
a[i] = get(1), tot--;
add(a[i], -1);
}
}
auto tmp2 = solve(std::vector<int>(a + 1, a + 1 + n));
for (int i = 0; i < n; i++) {
if (tmp[i] && tmp[i] != tmp2[i]) {
return puts("-1"), 0;
}
}
for (int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i == n];
return 0;
}WeChat Walk
给定 \(n\) 个点 \(m\) 条边的无向图，初始点权 0。\(q\) 天，每天增加一个点的点权，求每个点点权比周围的点都大的天数。
\(n, m, q \leq 2 \times 10^5\)，点权始终不会超过 \(10000\)
按照度数分类，度数大于 \(\sqrt{m}\) 的为大点，其余为小点。
大点不会超过 \(\sqrt m\) 个。
修改点权时，如果是小点，可以暴力更新周围点的情况。
如果是大点，分类讨论：
周围的大点，不会超过 \(\sqrt{m}\) 个，暴力更新。
周围的小点，不能暴力更新。
维护 \(max_i\) 表示大点周围小点权值的最大值，小点更新权值时更新。
观察数据范围，发现点权只有 \(10000\)，可以存下大点周围权值为 \(w\) 的有哪些小点是冠军。每次增加点权时暴力扫描权值更新小点。
容易发现每个大点最多扫描 \(q + w\) 次。
// Author: HolyK
// Created: Tue Jul 20 10:22:54 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(2e5 + 5), T(512);
std::vector<int> g[N], big[N], small[N / 512][10001];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, q;
std::cin >> n >> m >> q;
while (m--) {
int x, y;
std::cin >> x >> y;
x--, y--;
g[x].push_back(y);
g[y].push_back(x);
}
std::vector<int> id(n), b;
for (int i = 0; i < n; i++) {
if (g[i].size() > T) {
id[i] = b.size();
b.push_back(i);
for (int j : g[i]) {
big[j].push_back(id[i]);
}
}
}
std::vector<int> w(n), s(n), max(b.size()), ans(n);
for (int t = 1; t <= q; t++) {
int x, y;
std::cin >> x >> y;
x--;
if (g[x].size() <= T) {
if (!s[x]) {
int max = 0;
for (int i : g[x]) {
smax(max, w[i]);
if (s[i] && w[x] + y >= w[i]) {
ans[i] += t - s[i];
s[i] = 0;
}
}
if (w[x] + y > max) {
s[x] = t;
}
}
for (int i : big[x]) {
if (s[x]) small[i][w[x] + y].push_back(x);
smax(max[i], w[x] + y);
}
} else {
if (!s[x]) {
int m = max[id[x]];
for (int v : big[x]) {
int i = b[v];
smax(m, w[i]);
if (s[i] && w[x] + y >= w[i]) {
ans[i] += t - s[i];
s[i] = 0;
}
}
if (w[x] + y > m) s[x] = t;
for (int i = w[x] + y; i > w[x]; i--) {
for (int j : small[id[x]][i]) {
if (s[j] && i == w[j]) {
ans[j] += t - s[j];
s[j] = 0;
}
}
}
}
}
w[x] += y;
}
for (int i = 0; i < n; i++) {
if (s[i]) {
ans[i] += q - s[i];
}
}
for (int x : ans) {
std::cout << x << "\n";
}
return 0;
}最后修改于 2022-06-21