Editorial for Cho kẹo hay bị ghẹo
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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;
}
Comments