Сначала держи тупую реализацию (циклы - ложь):
#include <iostream>
using namespace std;
int a[1e5], n, answ = 1;
void pr(int ind)
{
if (ind == n) return;
answ *= a[ind];
pr(ind+1);
}
int main()
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
pr(0);
cout << answ;
------------------------------------------------
А вот нормальный алгоритм (Дерево отрезков). Если все же нужны изменения массива, то скину update.
#include <vector>
int n;
vector<int> a;
template<typename T>
struct seg_tree
T e;
T operation(T a, T b){};
void build();
void update(int pos, T value){};
T func(int L, int R) {};
};
vector<int> t;
// нумерация с 1 ( t[1] = func[0, n) )
void build(int v = 1, int tl = 0, int tr = n)
if (tr - tl == 1) // [x; x+1) == {x}
t[v] = a[tl];
return;
int mid = (tl + tr) / 2;
build(2*v, tl, mid);
build(2*v + 1, mid, tr);
t[v] = t[2*v] * t[2*v + 1];
int func(int L, int R, int v = 1, int tl = 0, int tr = n)
if (tr <= L || R <= tl) return 0;
if (L <= tl && tr <= R) return t[v];
return func(L, R, 2*v, tl, mid) * func(L, R, 2*v + 1, mid, tr);
t.resize(4*n,1); // чтобы точно хватило
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
build();
int l, r;
cout << func(0, n);
Copyright © 2024 SCHOLAR.TIPS - All rights reserved.
Answers & Comments
Сначала держи тупую реализацию (циклы - ложь):
#include <iostream>
using namespace std;
int a[1e5], n, answ = 1;
void pr(int ind)
{
if (ind == n) return;
answ *= a[ind];
pr(ind+1);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
pr(0);
cout << answ;
}
------------------------------------------------
А вот нормальный алгоритм (Дерево отрезков). Если все же нужны изменения массива, то скину update.
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a;
template<typename T>
struct seg_tree
{
T e;
T operation(T a, T b){};
void build();
void update(int pos, T value){};
T func(int L, int R) {};
};
vector<int> t;
// нумерация с 1 ( t[1] = func[0, n) )
void build(int v = 1, int tl = 0, int tr = n)
{
if (tr - tl == 1) // [x; x+1) == {x}
{
t[v] = a[tl];
return;
}
int mid = (tl + tr) / 2;
build(2*v, tl, mid);
build(2*v + 1, mid, tr);
t[v] = t[2*v] * t[2*v + 1];
}
int func(int L, int R, int v = 1, int tl = 0, int tr = n)
{
if (tr <= L || R <= tl) return 0;
if (L <= tl && tr <= R) return t[v];
int mid = (tl + tr) / 2;
return func(L, R, 2*v, tl, mid) * func(L, R, 2*v + 1, mid, tr);
}
int main()
{
cin >> n;
t.resize(4*n,1); // чтобы точно хватило
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
build();
int l, r;
cout << func(0, n);
}