Hướng dẫn giải của Cho kẹo hay bị ghẹo
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Subtask 1
Mô phỏng lại trò chơi trong độ phức tạp ~O(NQ)~.
Subtask 2
Độ phức tạp ~O(QlogN)~.
Vì tất cả số đều chẵn, nên với mỗi query tất cả các viên kẹo trong đoạn ~[L, R]~ đều được bỏ vào giỏ. Như vậy bài toán của chúng ta trở thành tìm max của đoạn con cho trước.
- Để tìm giá trị max trong đoạn ~[L, R]~, ta dùng CTDL Segment Tree.
- Để tính số lượng giá trị ~val \le 10^5~ trong một đoạn ~[L, R]~, ta có thể làm như sau.
- Gọi
vector<int> pos[val]là tập hợp các vị trí của ~val~ trong mảng theo thứ tự tăng dần. - Số lượng phần tử có giá trị ~val~ trong đoạn sẽ bằng
upper_bound(pos[val].begin(), pos[val].end(), R) - lower_bound(pos[val.begin(), pos[val].end(), L).
- Gọi
Subtask 3
Độ phức tạp ~O(QlogN)~.
Với mỗi số nguyên tố ~pr~ ta lưu vector<int> posPr[pr] là tập hợp các vị trí phần tử chia hết cho pr. Để tính mảng này, ta tiến hành phân tích các thừa số nguyên tố của ~A_i~ bằng sàng nguyên tố rồi cập nhật vào pos[val].
Lưu ý rằng với cách làm này, độ phức tạp không gian sẽ chỉ là ~O(nlog(A_i))~. Vì mỗi phần tử sẽ cập nhật cho tối đa ~O(log(A_i))~ thừa số nguyên tố.
Với tập vị trí của mỗi số nguyên tố ~p~, ta dựng một Segment Tree để tìm max các phần tử trong tập. Khi đó, để trả lời query, ta xét từng thừa số nguyên tố ~p~ của ~X~, rồi tìm phần tử lớn nhất chia hết cho ~p~ trong đoạn ~[L, R]~. Đáp án sẽ là giá trị lớn nhất trong các kết quả tìm được. Sau đó ta áp dụng cách đếm phần tử có giá trị cho trước trong đoạn ~[L, R]~ tương tự như sub 2.
Code trả lời query sẽ tương tự như sau:
int best = -1e9;
while (x > 1) {
int p = pr[x];
maximize(best, getMax(p, l, r));
while (x%p == 0) x /= p;
}
if (best < 0) cout << "-1 -1\n";
else {
int num = upper_bound(ALL(pos[best]), r) - lower_bound(ALL(pos[best]), l);
cout << best << ' ' << num << '\n';
}
Code tham khảo:
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n, q;
const int N = 1e5+5;
int a[N];
int pr[N];
vi pos[N];
vi posPr[N];
int par[2*N], siz[2*N];
class SegmentTree {
private:
int n;
vi node;
void build(int p, int b, int e, vi &idx) {
if (b == e) node[p] = a[idx[b]];
else {
int mid = (b+e) >> 1;
build(p<<1, b, mid, idx);
build((p<<1)|1, mid+1, e, idx);
node[p] = max(node[p<<1], node[(p<<1)|1]);
}
}
int getMax(int L, int R, int p, int b, int e) {
if (e < L || R < b || L > R) return -1e9;
if (L <= b && e <= R) return node[p];
int mid = (b+e) >> 1;
return max(getMax(L, R, p<<1, b, mid), getMax(L, R, (p<<1)|1, mid+1, e));
}
public:
void assign(int _n) {
n = _n;
node.assign(4*n+4, 0);
}
int getMax(int L, int R) {
return getMax(L, R, 1, 0, n-1);
}
void build(vi &idx) {
build(1, 0, n-1, idx);
}
};
SegmentTree trees[N];
void sieve() {
iota(pr, pr+N, 0);
pr[0] = pr[1] = -1;
for(int i = 2; i*i < N; i++) if (pr[i] == i) {
for(int j = i*i; j < N; j += i)
pr[j] = i;
}
}
void Input() {
cin >> n >> q;
FOR(i, 1, n) cin >> a[i];
}
int getMax(int p, int l, int r) {
int treeL = lower_bound(ALL(posPr[p]), l) - posPr[p].begin();
int treeR = upper_bound(ALL(posPr[p]), r) - posPr[p].begin()-1;
return trees[p].getMax(treeL, treeR);
}
void prepare() {
sieve();
FOR(i, 1, n) pos[a[i]].pb(i);
FOR(i, 1, n) {
int tmp = a[i];
while (tmp > 1) {
int p = pr[tmp];
posPr[p].pb(i);
while (tmp%p == 0) tmp /= p;
}
}
FOR(i, 1, N-1) if (posPr[i].size()) {
trees[i].assign(posPr[i].size());
trees[i].build(posPr[i]);
}
}
void Solve() {
prepare();
while (q--) {
int x, l, r; cin >> x >> l >> r;
int best = -1e9;
while (x > 1) {
int p = pr[x];
maximize(best, getMax(p, l, r));
while (x%p == 0) x /= p;
}
if (best < 0) cout << "-1 -1\n";
else {
int num = upper_bound(ALL(pos[best]), r) - lower_bound(ALL(pos[best]), l);
cout << best << ' ' << num << '\n';
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
Input(), Solve();
return 0;
}
Bình luận