вам дают массив [1… n] целых числа (1 ≤ a ≤ 10^9).
Мы называем subarray [i, j] (с 1 ≤ i
- 1 < n ≤ 5·10^4, 1 ≤ q ≤ 10^5
- 1 ≤ a ≤ 10^9
- В каждом запросе: 1 ≤ ℓ
Мое решение: < /strong>
Я реализовал следующее решение C ++, которое отвечает на каждый запрос, уменьшив к Blocks GCD и использованию автономного 2D Fenwick Tree. Это работает правильно, но TLE на самых больших тестах. Как я могу улучшить его асимптотическую сложность?#include
#include
#include
#include // for std::gcd
using namespace std;
using ll = long long;
/// One-dimensional Fenwick Tree (Binary Indexed Tree) supporting prefix sums
struct Fenwick1D {
int size;
vector tree;
void init(int n) {
size = n;
tree.assign(n + 1, 0);
}
// Add `value` to position `index`
void add(int index, ll value) {
for (; index 0; index -= index & -index)
sum += tree[index];
return sum;
}
};
/// 2D Fenwick Tree supporting range additions and prefix sum queries
/// over dynamic rectangular coordinates
struct Fenwick2D {
int size;
vector yCoordinates; // compressed y-values per x
vector tree1, tree2;
void init(int n) {
size = n;
yCoordinates.assign(n + 1, {});
}
// Stage 1: collect all (x, y) coordinates that will ever be used
void registerUpdate(int x, int y) {
for (int i = x; i n >> q;
vector a(n + 1);
for (int i = 1; i > a;
// Edge case: if the array is too small, all answers are zero
if (n < 2) {
while (q--) {
int l, r, k;
cin >> l >> r >> k;
cout > queries.left >> queries.right >> queries.gcdThreshold;
queries.index = i;
}
sort(queries.begin(), queries.end(), [](const auto &a, const auto &b) {
return a.gcdThreshold > b.gcdThreshold;
});
// Step 6: Sort positive GCD blocks by descending GCD
sort(positiveGCDBlocks.begin(), positiveGCDBlocks.end(), [](const auto &a, const auto &b) {
return a.gcdValue > b.gcdValue;
});
// Step 7: Answer each query using sweeping window and 2D Fenwick tree
vector results(q);
int blockPointer = 0;
auto queryRectangle = [&](int x, int y) -> ll {
if (x
Подробнее здесь: https://stackoverflow.com/questions/797 ... sting-suba
