автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵
↵
[tutorial:1946A]↵
↵
автор: [user:max0000561,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[tutorial:1946B]↵
↵
автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵
↵
[tutorial:1946C]↵
↵
автор: [user:azureglow,2024-03-22], разработчик: [user:azureglow,2024-03-22]↵
↵
[tutorial:1946D]↵
↵
автор: [user:yunetive29,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[tutorial:1946E]↵
↵
автор: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22], разработчик: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22]↵
↵
[tutorial:1946F]problem:1946A]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946A]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using i64 = long long;↵
↵
void solve() {↵
int n;↵
std::cin >> n;↵
std::vector<int> a(n);↵
for (int i = 0; i < n; i++) {↵
std::cin >> a[i];↵
}↵
std::sort(a.begin(), a.end());↵
int p = (n + 1) / 2 - 1;↵
int res = std::count(a.begin() + p, a.end(), a[p]);↵
std::cout << res << "\n";↵
}↵
↵
signed main() {↵
std::ios::sync_with_stdio(false);↵
std::cin.tie(nullptr);↵
↵
int t = 1;↵
std::cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:max0000561,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[problem:1946B]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946B]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int P = 1e9 + 7;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
int S = 0, sum = 0;↵
int cur = 0;↵
for (int i = 0; i < n; i++) {↵
sum += a[i];↵
cur += a[i];↵
cur = max(cur, 0LL);↵
S = max(S, cur);↵
}↵
sum = (sum % P + P) % P;↵
S = S % P;↵
int t = 1;↵
for (int i = 0; i < k; i++) {↵
t = t * 2 % P;↵
}↵
int ans = (sum + S * t - S + P) % P;↵
cout << ans << '\n';↵
}↵
↵
↵
signed main() {↵
//cout << fixed << setprecision(20);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1, G = 1;↵
//cin >> G;↵
cin >> T;↵
while (T--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵
↵
[problem:1946C]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946C]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using i64 = long long;↵
↵
void solve() {↵
int n, k;↵
std::cin >> n >> k;↵
std::vector<std::vector<int>> adj(n);↵
for (int i = 0; i < n - 1; i++) {↵
int v, u;↵
std::cin >> v >> u;↵
--v, --u;↵
adj[v].emplace_back(u);↵
adj[u].emplace_back(v);↵
}↵
auto check = [&](int x) {↵
int res = 0;↵
auto dfs = [&](auto self, int v, int f) -> int {↵
int sz = 1;↵
for (int u : adj[v]) {↵
if (u == f) {↵
continue;↵
}↵
sz += self(self, u, v);↵
}↵
if (sz >= x && f != v) {↵
++res, sz = 0;↵
}↵
return sz;↵
};↵
int t = dfs(dfs, 0, 0);↵
return (res > k || (t >= x && res == k) ? true : false);↵
};↵
int low = 1, high = n / (k + 1) + 1;↵
while (high - low > 1) {↵
int mid = (low + high) / 2;↵
if (check(mid)) {↵
low = mid;↵
} else {↵
high = mid;↵
}↵
}↵
std::cout << low << "\n";↵
}↵
↵
signed main() {↵
std::ios::sync_with_stdio(false);↵
std::cin.tie(nullptr);↵
↵
int t = 1;↵
std::cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:azureglow,2024-03-22], разработчик: [user:azureglow,2024-03-22]↵
↵
[problem:1946D]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946D]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
#define int ll↵
#define all(a) a.begin(), a.end()↵
↵
void solve() {↵
int n, x;↵
cin >> n >> x;↵
++x;↵
vector<int> a(n);↵
for (int &i: a)↵
cin >> i;↵
int res = -1;↵
for (int i = 30; i >= 0; --i) {↵
vector<int> b;↵
bool open = false;↵
for (int j = 0; j < a.size(); ++j) {↵
if (!open)↵
b.push_back(a[j]);↵
else↵
b.back() ^= a[j];↵
if (a[j] & (1 << i))↵
open = !open;↵
}↵
if (!(x & (1 << i))) {↵
if (open) {↵
cout << res << '\n';↵
return;↵
}↵
a = b;↵
} else {↵
if (!open)↵
res = max(res, (int) b.size());↵
}↵
}↵
cout << res << '\n';↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int t = 1;↵
cin >> t;↵
while (t--)↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Решение (74TrAkToR)">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
int const maxn = 1e5 + 5;↵
int a[maxn];↵
↵
int solve(int n, int x) {↵
int res = 0, curr = 0;↵
for (int i = 1; i <= n; i++) {↵
curr ^= a[i];↵
if ((curr|x) == x) curr = 0, res++;↵
else {↵
if (i == n) return -1;↵
}↵
}↵
return res;↵
}↵
↵
main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, x;↵
cin >> n >> x;↵
for (int i = 1; i <= n; i++) cin >> a[i];↵
int ans = -1;↵
ans = max(ans, solve(n, x));↵
for (int b = 29; b >= 0; b--) {↵
if ((x>>b)&1) {↵
int y = (x^(1 << b));↵
for (int c = b - 1; c >= 0; c--) {↵
if (((y>>c)&1) == 0) y ^= (1 << c);↵
}↵
ans = max(ans, solve(n, y));↵
}↵
}↵
cout << ans << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:yunetive29,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[problem:1946E]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946E]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define eb emplace_back↵
#define int long long↵
const int N = 200200, P = 1e9 + 7;↵
int fact[N], reverse_fact[N];↵
↵
int binpow(int x, int n) {↵
if (n == 0)↵
return 1;↵
if (n == 1)↵
return x;↵
int t = binpow(x, n / 2);↵
t = t * t % P;↵
if (n % 2 == 1)↵
t = t * x % P;↵
return t;↵
}↵
↵
int inv(int x) {↵
return binpow(x, P - 2);↵
}↵
↵
void precalc() {↵
fact[0] = 1;↵
for (int i = 1; i < N; i++)↵
fact[i] = fact[i - 1] * i % P;↵
for (int i = 0; i < N; i++)↵
reverse_fact[i] = inv(fact[i]);↵
}↵
↵
int C(int n, int k) {↵
return fact[n] * reverse_fact[k] % P * reverse_fact[n - k] % P;↵
}↵
↵
int f(int a, int b) {↵
return C(a + b, b);↵
}↵
↵
vector<vector<int>> g;↵
vector<int> dp, siz;↵
↵
void dfs(int v) {↵
int cnt = 0, x = -1, y = -1;↵
for (auto to : g[v]) {↵
dfs(to);↵
siz[v] += siz[to];↵
if (siz[to] == 1)↵
cnt++;↵
else if (x == -1)↵
x = to;↵
else↵
y = to;↵
}↵
if (x == -1)↵
dp[v] = fact[cnt];↵
else if (y == -1)↵
dp[v] = dp[x] * fact[cnt] % P * f(siz[x], cnt) % P;↵
else↵
dp[v] = dp[x] * dp[y] % P * f(siz[x], siz[y]) % P;↵
}↵
↵
↵
void solve() {↵
int n, m1, m2;↵
cin >> n >> m1 >> m2;↵
vector<int> pref(m1), suf(m2);↵
for (auto &it : pref)↵
cin >> it;↵
for (auto &it : suf)↵
cin >> it;↵
for (auto &it : pref)↵
it--;↵
for (auto &it : suf)↵
it--;↵
g.assign(n, {});↵
dp.assign(n, 1);↵
siz.assign(n, 1);↵
if (pref.back() != suf.front() || pref.front() != 0 || suf.back() != n - 1) {↵
cout << 0 << '\n';↵
return;↵
}↵
for (int i = m1 - 1; i > 0; i--) {↵
g[pref[i]].eb(pref[i - 1]);↵
for (int j = pref[i] - 1; j > pref[i - 1]; j--)↵
g[pref[i - 1]].eb(j);↵
}↵
for (int i = 0; i < m2 - 1; i++) {↵
g[suf[i]].eb(suf[i + 1]);↵
for (int j = suf[i] + 1; j < suf[i + 1]; j++)↵
g[suf[i + 1]].eb(j);↵
}↵
dfs(pref.back());↵
cout << dp[pref.back()] << '\n';↵
}↵
↵
↵
signed main() {↵
//cout << fixed << setprecision(20);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1, G;↵
//cin >> G;↵
precalc();↵
cin >> T;↵
while (T--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
автор: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22], разработчик: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22]↵
↵
[problem:1946F]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946F]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using i64 = long long;↵
↵
template<class Info>↵
struct Fenwick {↵
std::vector<Info> t;↵
int n;↵
↵
Fenwick(int n = 0) : n(n) {↵
t.resize(n);↵
}↵
↵
void add(int x, const Info &v) {↵
for (int i = x + 1; i <= n; i += i & -i) {↵
t[i - 1] = t[i - 1] + v;↵
}↵
}↵
↵
Info sum(int x) {↵
x++;↵
Info res = Info();↵
for (int i = x; i > 0; i -= i & -i) {↵
res = res + t[i - 1];↵
}↵
return res;↵
}↵
↵
Info rangeSum(int l, int r) {↵
Info res = sum(r) - sum(l - 1);↵
return res;↵
}↵
};↵
↵
void solve() {↵
int n, q;↵
std::cin >> n >> q;↵
std::vector<int> a(n), pos(n + 1);↵
for (int i = 0; i < n; i++) {↵
std::cin >> a[i];↵
}↵
std::reverse(a.begin(), a.end());↵
for (int i = 0; i < n; i++) {↵
pos[a[i]] = i;↵
}↵
constexpr int K = 19;↵
std::vector<i64> res(q);↵
std::vector<std::vector<std::pair<int, int>>> qry(n);↵
for (int i = 0; i < q; i++) {↵
int l, r;↵
std::cin >> l >> r;↵
l--, r--;↵
std::swap(l, r);↵
l = n - l - 1;↵
r = n - r - 1;↵
qry[r].emplace_back(l, i);↵
}↵
std::vector<i64> dp(n + 1);↵
Fenwick<i64> f(n);↵
for (int r = 0; r < n; r++) {↵
int x = a[r];↵
dp[x] = 1;↵
// n * log(n) * log(n)↵
for (int y = x; y <= n; y += x) {↵
if (pos[y] > pos[x]) {↵
continue;↵
}↵
for (int z = 2 * y; z <= n; z += y) {↵
if (pos[z] > pos[y]) {↵
continue;↵
}↵
dp[z] += dp[y];↵
}↵
}↵
// n * log(n) * log(n)↵
for (int y = x; y <= n; y += x) {↵
f.add(pos[y], dp[y]);↵
dp[y] = 0;↵
}↵
// q * log(n)↵
for (auto [l, i] : qry[r]) {↵
res[i] += f.rangeSum(l, r);↵
}↵
}↵
for (int i = 0; i < q; i++) {↵
std::cout << res[i] << " \n"[i == q - 1];↵
}↵
}↵
↵
signed main() {↵
std::ios::sync_with_stdio(false);↵
std::cin.tie(nullptr);↵
↵
int t = 1;↵
std::cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[
↵
автор: [user:max0000561,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[tutorial:1946B]↵
↵
автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵
↵
[tutorial:1946C]↵
↵
автор: [user:azureglow,2024-03-22], разработчик: [user:azureglow,2024-03-22]↵
↵
[tutorial:1946D]↵
↵
автор: [user:yunetive29,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[tutorial:1946E]↵
↵
автор: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22], разработчик: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22]↵
↵
[tutorial:1946F]
↵
<spoiler summary="Разбор">↵
[tutorial:1946A]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using i64 = long long;↵
↵
void solve() {↵
int n;↵
std::cin >> n;↵
std::vector<int> a(n);↵
for (int i = 0; i < n; i++) {↵
std::cin >> a[i];↵
}↵
std::sort(a.begin(), a.end());↵
int p = (n + 1) / 2 - 1;↵
int res = std::count(a.begin() + p, a.end(), a[p]);↵
std::cout << res << "\n";↵
}↵
↵
signed main() {↵
std::ios::sync_with_stdio(false);↵
std::cin.tie(nullptr);↵
↵
int t = 1;↵
std::cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:max0000561,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[problem:1946B]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946B]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int P = 1e9 + 7;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
int S = 0, sum = 0;↵
int cur = 0;↵
for (int i = 0; i < n; i++) {↵
sum += a[i];↵
cur += a[i];↵
cur = max(cur, 0LL);↵
S = max(S, cur);↵
}↵
sum = (sum % P + P) % P;↵
S = S % P;↵
int t = 1;↵
for (int i = 0; i < k; i++) {↵
t = t * 2 % P;↵
}↵
int ans = (sum + S * t - S + P) % P;↵
cout << ans << '\n';↵
}↵
↵
↵
signed main() {↵
//cout << fixed << setprecision(20);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1, G = 1;↵
//cin >> G;↵
cin >> T;↵
while (T--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:exhausted,2024-03-22], разработчик: [user:exhausted,2024-03-22]↵
↵
[problem:1946C]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946C]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using i64 = long long;↵
↵
void solve() {↵
int n, k;↵
std::cin >> n >> k;↵
std::vector<std::vector<int>> adj(n);↵
for (int i = 0; i < n - 1; i++) {↵
int v, u;↵
std::cin >> v >> u;↵
--v, --u;↵
adj[v].emplace_back(u);↵
adj[u].emplace_back(v);↵
}↵
auto check = [&](int x) {↵
int res = 0;↵
auto dfs = [&](auto self, int v, int f) -> int {↵
int sz = 1;↵
for (int u : adj[v]) {↵
if (u == f) {↵
continue;↵
}↵
sz += self(self, u, v);↵
}↵
if (sz >= x && f != v) {↵
++res, sz = 0;↵
}↵
return sz;↵
};↵
int t = dfs(dfs, 0, 0);↵
return (res > k || (t >= x && res == k) ? true : false);↵
};↵
int low = 1, high = n / (k + 1) + 1;↵
while (high - low > 1) {↵
int mid = (low + high) / 2;↵
if (check(mid)) {↵
low = mid;↵
} else {↵
high = mid;↵
}↵
}↵
std::cout << low << "\n";↵
}↵
↵
signed main() {↵
std::ios::sync_with_stdio(false);↵
std::cin.tie(nullptr);↵
↵
int t = 1;↵
std::cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:azureglow,2024-03-22], разработчик: [user:azureglow,2024-03-22]↵
↵
[problem:1946D]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946D]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
#define int ll↵
#define all(a) a.begin(), a.end()↵
↵
void solve() {↵
int n, x;↵
cin >> n >> x;↵
++x;↵
vector<int> a(n);↵
for (int &i: a)↵
cin >> i;↵
int res = -1;↵
for (int i = 30; i >= 0; --i) {↵
vector<int> b;↵
bool open = false;↵
for (int j = 0; j < a.size(); ++j) {↵
if (!open)↵
b.push_back(a[j]);↵
else↵
b.back() ^= a[j];↵
if (a[j] & (1 << i))↵
open = !open;↵
}↵
if (!(x & (1 << i))) {↵
if (open) {↵
cout << res << '\n';↵
return;↵
}↵
a = b;↵
} else {↵
if (!open)↵
res = max(res, (int) b.size());↵
}↵
}↵
cout << res << '\n';↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int t = 1;↵
cin >> t;↵
while (t--)↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Решение (74TrAkToR)">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
int const maxn = 1e5 + 5;↵
int a[maxn];↵
↵
int solve(int n, int x) {↵
int res = 0, curr = 0;↵
for (int i = 1; i <= n; i++) {↵
curr ^= a[i];↵
if ((curr|x) == x) curr = 0, res++;↵
else {↵
if (i == n) return -1;↵
}↵
}↵
return res;↵
}↵
↵
main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, x;↵
cin >> n >> x;↵
for (int i = 1; i <= n; i++) cin >> a[i];↵
int ans = -1;↵
ans = max(ans, solve(n, x));↵
for (int b = 29; b >= 0; b--) {↵
if ((x>>b)&1) {↵
int y = (x^(1 << b));↵
for (int c = b - 1; c >= 0; c--) {↵
if (((y>>c)&1) == 0) y ^= (1 << c);↵
}↵
ans = max(ans, solve(n, y));↵
}↵
}↵
cout << ans << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
автор: [user:yunetive29,2024-03-22], разработчик: [user:yunetive29,2024-03-22]↵
↵
[problem:1946E]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946E]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define eb emplace_back↵
#define int long long↵
const int N = 200200, P = 1e9 + 7;↵
int fact[N], reverse_fact[N];↵
↵
int binpow(int x, int n) {↵
if (n == 0)↵
return 1;↵
if (n == 1)↵
return x;↵
int t = binpow(x, n / 2);↵
t = t * t % P;↵
if (n % 2 == 1)↵
t = t * x % P;↵
return t;↵
}↵
↵
int inv(int x) {↵
return binpow(x, P - 2);↵
}↵
↵
void precalc() {↵
fact[0] = 1;↵
for (int i = 1; i < N; i++)↵
fact[i] = fact[i - 1] * i % P;↵
for (int i = 0; i < N; i++)↵
reverse_fact[i] = inv(fact[i]);↵
}↵
↵
int C(int n, int k) {↵
return fact[n] * reverse_fact[k] % P * reverse_fact[n - k] % P;↵
}↵
↵
int f(int a, int b) {↵
return C(a + b, b);↵
}↵
↵
vector<vector<int>> g;↵
vector<int> dp, siz;↵
↵
void dfs(int v) {↵
int cnt = 0, x = -1, y = -1;↵
for (auto to : g[v]) {↵
dfs(to);↵
siz[v] += siz[to];↵
if (siz[to] == 1)↵
cnt++;↵
else if (x == -1)↵
x = to;↵
else↵
y = to;↵
}↵
if (x == -1)↵
dp[v] = fact[cnt];↵
else if (y == -1)↵
dp[v] = dp[x] * fact[cnt] % P * f(siz[x], cnt) % P;↵
else↵
dp[v] = dp[x] * dp[y] % P * f(siz[x], siz[y]) % P;↵
}↵
↵
↵
void solve() {↵
int n, m1, m2;↵
cin >> n >> m1 >> m2;↵
vector<int> pref(m1), suf(m2);↵
for (auto &it : pref)↵
cin >> it;↵
for (auto &it : suf)↵
cin >> it;↵
for (auto &it : pref)↵
it--;↵
for (auto &it : suf)↵
it--;↵
g.assign(n, {});↵
dp.assign(n, 1);↵
siz.assign(n, 1);↵
if (pref.back() != suf.front() || pref.front() != 0 || suf.back() != n - 1) {↵
cout << 0 << '\n';↵
return;↵
}↵
for (int i = m1 - 1; i > 0; i--) {↵
g[pref[i]].eb(pref[i - 1]);↵
for (int j = pref[i] - 1; j > pref[i - 1]; j--)↵
g[pref[i - 1]].eb(j);↵
}↵
for (int i = 0; i < m2 - 1; i++) {↵
g[suf[i]].eb(suf[i + 1]);↵
for (int j = suf[i] + 1; j < suf[i + 1]; j++)↵
g[suf[i + 1]].eb(j);↵
}↵
dfs(pref.back());↵
cout << dp[pref.back()] << '\n';↵
}↵
↵
↵
signed main() {↵
//cout << fixed << setprecision(20);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1, G;↵
//cin >> G;↵
precalc();↵
cin >> T;↵
while (T--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
автор: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22], разработчик: [user:exhausted,2024-03-22], [user:yunetive29,2024-03-22]↵
↵
[problem:1946F]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1946F]↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using i64 = long long;↵
↵
template<class Info>↵
struct Fenwick {↵
std::vector<Info> t;↵
int n;↵
↵
Fenwick(int n = 0) : n(n) {↵
t.resize(n);↵
}↵
↵
void add(int x, const Info &v) {↵
for (int i = x + 1; i <= n; i += i & -i) {↵
t[i - 1] = t[i - 1] + v;↵
}↵
}↵
↵
Info sum(int x) {↵
x++;↵
Info res = Info();↵
for (int i = x; i > 0; i -= i & -i) {↵
res = res + t[i - 1];↵
}↵
return res;↵
}↵
↵
Info rangeSum(int l, int r) {↵
Info res = sum(r) - sum(l - 1);↵
return res;↵
}↵
};↵
↵
void solve() {↵
int n, q;↵
std::cin >> n >> q;↵
std::vector<int> a(n), pos(n + 1);↵
for (int i = 0; i < n; i++) {↵
std::cin >> a[i];↵
}↵
std::reverse(a.begin(), a.end());↵
for (int i = 0; i < n; i++) {↵
pos[a[i]] = i;↵
}↵
constexpr int K = 19;↵
std::vector<i64> res(q);↵
std::vector<std::vector<std::pair<int, int>>> qry(n);↵
for (int i = 0; i < q; i++) {↵
int l, r;↵
std::cin >> l >> r;↵
l--, r--;↵
std::swap(l, r);↵
l = n - l - 1;↵
r = n - r - 1;↵
qry[r].emplace_back(l, i);↵
}↵
std::vector<i64> dp(n + 1);↵
Fenwick<i64> f(n);↵
for (int r = 0; r < n; r++) {↵
int x = a[r];↵
dp[x] = 1;↵
// n * log(n) * log(n)↵
for (int y = x; y <= n; y += x) {↵
if (pos[y] > pos[x]) {↵
continue;↵
}↵
for (int z = 2 * y; z <= n; z += y) {↵
if (pos[z] > pos[y]) {↵
continue;↵
}↵
dp[z] += dp[y];↵
}↵
}↵
// n * log(n) * log(n)↵
for (int y = x; y <= n; y += x) {↵
f.add(pos[y], dp[y]);↵
dp[y] = 0;↵
}↵
// q * log(n)↵
for (auto [l, i] : qry[r]) {↵
res[i] += f.rangeSum(l, r);↵
}↵
}↵
for (int i = 0; i < q; i++) {↵
std::cout << res[i] << " \n"[i == q - 1];↵
}↵
}↵
↵
signed main() {↵
std::ios::sync_with_stdio(false);↵
std::cin.tie(nullptr);↵
↵
int t = 1;↵
std::cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
