DIV X Разбор - Codeforces

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	156
6	adamant	152
6	djm03178	152
8	Qingyu	151
9	luogu_official	149
10	awoo	147

B задача

Разбор

Автор задачи : MisterGir

По условию задачи мы должны найти область города , где Rentaro подхватит меньшее количество женщин. Нам дается матрица $$$n * m$$$.

$$$1$$$ — клетка, в которой есть женщина.

$$$0$$$ — клетка, в которой стенка

Это задача строится на поиске лучшей области , которая состоит только из $$$1$$$. Для решения задачи можно использовать алгоритмы $$$dfs$$$ или $$$bfs$$$.

Давайте посчитаем количество единиц. Если в матрице нету единиц выводим $$$«Boring$$$ $$$life$$$ $$$in$$$ $$$high$$$ $$$school»$$$. Теперь давайте пройдем по матрице за $$$n * m$$$. Когда проходим матрицу смотрим элемент равен единице или нет. Если нет до идем дальше по матрице. Если да запускаем $$$dfs$$$ или $$$bfs$$$.

Автор использовал алгоритм $$$dfs$$$

dfs

void dfs(ll i,ll j)
{
    if (i < 0 || j < 0 || j > m - 1 || i > n - 1 || a[i][j] == 0)
   // i < 0         i > n - 1  j < 0         j > m - 1  смотрим не выходим ли мы за границы матрицы .
   // a[i][j] == 0 то это следует , что там женщины нету. Значит нам это клетка не надо

        return;
  // cnt --- количество женщин 
    cnt+=a[i][j];   // добавляем женщину
    a[i][j] = 0;    // мы ее уже добавили ,значит мы убираем из клетки женщину. 
    dfs(i - 1,j);   // идем вверх
    dfs(i , j - 1); // идем влево
    dfs(i,  j + 1); // идем вправо
    dfs(i + 1 , j); // идем вверх
}

Псевдокод

#include <bits/stdc++.h>
//#define Test
using ll = long long;
using namespace std;
ll cnt = 0;
ll n,m;
vector<vector<ll>> a;
void dfs(ll i,ll j)
{
    if (i < 0 || j < 0 || j > m - 1 || i > n - 1 || a[i][j] == 0)
        return;
    cnt+=a[i][j];
    a[i][j] = 0;
    dfs(i - 1,j);
    dfs(i , j - 1);
    dfs(i,  j + 1);
    dfs(i + 1 , j);
}

void Solve()
{
    cin >> n >> m;
    a = vector<vector<ll>>(n,vector<ll>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0 ;j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    ll ans = 1e18;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
             if (a[i][j] > 0)
             {
                 cnt = 0;
                 dfs(i,j);
                 ans = min(ans,cnt);
             }
        }
    }
    if (ans == 1e18)
    {
        cout << "Boring life in high school\n";
    }
    else
    {
        cout << ans << '\n';
    }


}
int main()
{
    //  freopen("test1.in","r",stdin);
    //  freopen("test1.out","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
   // cin>>tt;
    while(tt-->0)
    {
        Solve();
    }
}

C задача

Разбор

Автор задачи : Napoleon

Итак заметим что нам всегда будет выгодно использовать все планы. Наша задача свелась к поиску двух непересекающихся подпоследовательностей массива $$$A$$$, что произведение их сумм максимально. Давайте для этого найдем все возможные суммы, которые мы можем собрать в одной подпоследовательности. Тогда если возможна сумма $$$s_1$$$, то $$$s_2 = s - s_1$$$, где $$$s$$$ — сумма всего массива. Для поиска всех возможных сумм мы можем использовать стандартный алгоритм для решения задачи о рюкзаке. Также мы можем оптимизировать наше динамическое программирование добавив $$$bitset$$$.

Псевдокод 1

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main()
{
    ll n;
    cin>>n;
    vector<ll> vec(n);
    ll sum = 0;
    for (ll i=0;i<n;++i)
    {
        cin>>vec[i];
        sum += vec[i];
    }
    ll N = 1e5;
    vector<ll> dp(N+1,-1);
    ll ans =0;
    ll cur = 1;
    dp[0] = 0;
    for (ll i=0;i<n;++i)
    {
        for (ll s = 0;s<=N;++s)
        {
            if (dp[s] != cur && dp[s + vec[i]]==-1 && dp[s] !=-1)
            {
                dp[s + vec[i]] = cur;
            }
        }
        cur ++;
    }
    for (ll i=0;i<=N;++i)
    {
        if (dp[i]== -1)
        {
            continue;
        }
        ans = max(ans,i * (sum-i));
    }
    cout<<ans;

}

Псевдокод 2

#include <bits/stdc++.h>
using namespace std;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n; cin >> n;
    vector<int> a(n + 1);
    int s = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s += a[i];
    }
    bitset<200001> dp;
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp |= dp << a[i];
    }
    int ans = 0;
    for (int i = 0; i <= 200000; ++i) {
        if (dp[i] == 1) {
            ans = max(ans, i * (s - i));
        }
    }
    cout << ans << endl;
    return 0;
}

D задача

Разбор

Автор задачи : MisterGir

В этой задаче мы должны знать формулы

Для первого типа запроса

$$$\left(\frac{n(n + 1)}{2} \right.)$$$

Для второго типа запроса

$$$\left(\frac{n(n + 1)(2n + 1)}{6} \right.)$$$

Доказательство 1 формулы

1 формула

Доказательство 2 формулы

2 формула

Но большая сложность в задаче была написание длинной арифметики для $$$C++$$$ или $$$ СИ $$$ или знания __int128. Можно сказать в этой задаче очень повезло питонистам. В языке $$$Python$$$ есть встроенная длинная арифметика из — за этого задача для них была легка.

Псевдокод с++ int128

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
using llt = __int128_t;
void print(llt z){
	string s;
	while(z){
		s.push_back('0' + (z % 10));
		z /= 10;
	}
	reverse(s.begin(),s.end());
	cout << s << '\n';
}

void Solve()
{
    ll q;
    cin >> q;
    while (q-->0)
    {
        ll tp, l, r; cin >> tp >> l >> r;
		if(l >= r){
			cout << 0 << '\n';
		}
		else{
			if(tp == 1){
				llt L = (llt)(l) * (l+1) / 2;
				llt R = (llt)(r) * (r+1) / 2;
				print(R - L);
			}
			else{
				llt L = (llt)(l) * (l+1) * (2*l+1) / 6;
				llt R = (llt)(r) * (r+1) * (2*r+1) / 6;
				print(R - L);
			}
		}
    }


}
int main()
{
    //  freopen("input.txt","r",stdin);
    //  freopen("output.txt","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    //cin >> tt;
    while (tt-->0)
    {
        Solve();
        // cout << '\n';
    }
}

Псевдокод с++

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
struct bigint {

    static const ll base = 1e9;
    static const ll len = 10;

    ll digits[len];

    bigint() {
        for (int i = 0; i < len; i++) {
            digits[i] = 0;
        }
    }

    bigint(ll x) {
        for (int i = 0; i < len; i++) {
            digits[i] = 0;
        }

        int next = 0;
        while (x) {
            digits[next++] = x % base;
            x /= base;
        }
    }

    bigint(const bigint& other) {
        for (int i = 0; i < len; i++) {
            digits[i] = other.digits[i];
        }
    }

    bigint& operator=(const bigint& other) {
        for (int i = 0; i < len; i++) {
            digits[i] = other.digits[i];
        }

        return *this;
    }

    void operator+=(const bigint& other) {
        for (int i = 0; i < len; i++) {
            digits[i] += other.digits[i];
        }

        for (int i = 0; i < len - 1; i++) {
            if (digits[i] >= base) {
                digits[i] -= base;
                digits[i + 1]++;
            }
        }
    }

    bigint operator+(const bigint& other) {
        bigint n(*this);
        n += other;
        return n;
    }

    bigint& operator++() {
        *this += 1;
        return *this;
    }

    void operator-=(const bigint& other) {
        for (int i = 0; i < len; i++) {
            digits[i] -= other.digits[i];
        }

        for (int i = 0; i < len - 1; i++) {
            if (digits[i] < 0) {
                digits[i] += base;
                digits[i + 1]--;
            }
        }
    }

    bigint operator-(const bigint& other) {
        bigint n(*this);
        n -= other;
        return n;
    }

    bigint& operator--() {
        *this -= 1;
        return *this;
    }

    void operator*=(const bigint& other) {
        *this = *this * other;
    }

    bigint operator*(const bigint& other) {
        bigint result;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                result.digits[i + j] += digits[i] * other.digits[j];
            }
        }

        for (int i = 0; i < len - 1; i++) {
            result.digits[i + 1] += result.digits[i] / base;
            result.digits[i] %= base;
        }

        return result;
    }

    void operator/=(ll x) {
        for (int i = len - 1; i >= 0; i--) {
            if (i) {
                digits[i - 1] += (digits[i] % x) * base;
            }

            digits[i] /= x;
        }
    }

    bigint operator/(ll x) {
        bigint n(*this);
        n /= x;
        return n;
    }
};

ostream& operator<<(ostream& out, const bigint& num) {
    string result;

    char buffer[10];

    for (int i = bigint::len - 1; i >= 0; i--) {
        sprintf(buffer, "%09d", num.digits[i]);
        result += buffer;
    }

    int first_idx = result.find_first_not_of('0');
    if (first_idx == string::npos) {
        out << "0";
    } else {
        out << result.substr(first_idx);
    }

    return out;
}

bigint formulsquare(ll n)
{
    bigint res =  n;
    res *= (n + 1);
    res *= (2 * n + 1);
    res /= 6;
    return res;
}
bigint formul(ll n)
{
    bigint res = n;
    res *= (n + 1);
    res /= 2;
    return res;
}

void Solve()
{
    ll q;
    cin >> q;
    while (q-->0)
    {
        ll type;
        cin >> type;
        if (type == 1)
        {
            ll L, R ;
            cin >> L >> R;
            cout << formul(R) - formul(L) << '\n';
        }
        else
        {

            ll L, R ;
            cin >> L >> R;
            cout << formulsquare(R) - formulsquare(L) << '\n';
        }
    }


}
int main()
{
    // freopen("input.txt","r",stdin);
    // freopen("14.txt","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
  //  cin >> tt;
    while (tt-->0)
    {
        Solve();
        // cout << '\n';
    }
}

Псевдокод python

def formulsquare(n):
    res = n * (n + 1) * (2 * n + 1) // 6
    return res

def formul(n):
    res = n * (n + 1) // 2
    return res

def Solve():
    q = int(input())
    while q > 0:
        q -= 1
        type, L, R = map(int, input().split()) 
        if type == 1:
            print(formul(R) - formul(L))
        else:
            print(formulsquare(R) - formulsquare(L))

def main():
    #  freopen("input.txt","r",stdin);
    #  freopen("output.txt","w",stdout);
    tt = 1
    #tt = int(input())
    while tt > 0:
        tt -= 1
        Solve()
        # print('\n')

if __name__ == "__main__":
    main()

E задача

Разбор

Автор задачи : MisterGir

Это задача построена на знание Решето Эратосфены(теория)

Псевдокод Решето Эратосфены

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    for (int i = 2; i <= n; i++)
        if (is_prime[i])
            for (int j = 2 * i; j <= n; j += i)
                is_prime[j] = false;
    return is_prime;            
}

Давайте изменим это код . Так чтобы мы хранили минимальный простой множитель в решето Эратосфены.

Например :

Нам дается числа $$$2$$$ $$$3$$$ $$$6$$$ $$$8$$$

В Решето Эратосфены , где представлен в "Псевдокод Решето Эратосфены". У нас простые числа были бы $$$2$$$ , $$$3$$$. А теперь меняем логику для нашего решето , будем хранить минимальный простой множитель

Создаем массив $$$Reheto$$$ размером $$$10 ^ 6 + 5$$$. Теперь давайте пройдем по ему и запишем минимальный множитель. Например для чисел $$$2$$$ $$$3$$$ $$$6$$$ $$$8$$$ $$$10$$$ $$$23$$$ в Решете будет хранится

$$$Reheto_2 = 2$$$;

$$$Reheto_3 = 3$$$;

$$$Reheto_6 = 2$$$;

$$$Reheto_8 = 2$$$;

$$$Reheto_{10} = 2$$$;

$$$Reheto_{23} = 23$$$;

Т.к нам нужен минимальный множитель , который $$$>$$$ $$$1$$$.

Теперь давайте разберем число $$$6$$$ как пример. В Решете у нас в $$$Reheto_6$$$ является двойка.

Давайте выведем , и после этого делим $$$6$$$ на $$$2$$$,и получается $$$3$$$

Теперь смотрим в $$$Reheto_3$$$ хранится $$$3$$$ . Давайте делить $$$3$$$ , и после операции у нас получается $$$1$$$.

Для $$$6$$$ является ответом $$$2$$$ $$$3$$$. Проверяем $$$2 * 3 = 6$$$ — значит это правда.

Теперь давайте проверим случаи, когда это не возможно.

Это будет $$$1$$$ , а также $$$0$$$. Т.к в теории чисел, простые множители (простые делители) положительного целого числа — это простые числа, которые делят это число нацело (без остатка). Выделить простые множители положительного целого числа означает перечислить эти простые множители вместе с их кратностями.

Псевдокод 1

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ll = long long;
using namespace std;
const ll N = 1e6 + 5;
ll lp[N];
vector<ll> pr;
void precalc()
{
    for (ll i = 2; i < N; ++i)
    {
        if (lp[i] == 0)
        {
            lp[i] = i;
            pr.push_back(i);
        }
        for (ll j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] < N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}
void factorize(ll n)
{
    while (n > 1)
    {
        cout << lp[n] << ' ';
        n /= lp[n];
    }
    cout << '\n';
}
void Solve()
{
    ll x;
    cin >> x;
    if (x != 1 && x != 0)
    {
        factorize(x);
    }
    else
    {
        cout << "No answer\n";
    }


}
int main()
{
    // freopen("input.txt","r",stdin);
    //  freopen("output.txt","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    precalc();
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
        // cout << '\n';
    }
}

Псевдокод 2

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n = 1e6 + 6;
    vector<int> p(n + 1);
    for (int i = 2; i <= n; ++i) {
        if (p[i] != 0) {
            continue;
        }
        for (int j = i; j <= n; j += i) {
            if (p[j] == 0) p[j] = i;
            else p[j] = min(p[j], i);
        }
    }
    int q; cin >> q;
    while (q--) {
        int q; cin >> q;
        if (q <= 1) {
            cout << "No answer\n";
            continue;
        }
        while (q != 1) {
            int v = p[q];
            while (q % v == 0) {
                q /= v;
                cout << v << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

F задача

Разбор

Автор задачи : MegaEnderman2009

По сути в задаче нам нужно решить линейное диофантово уравнение вида $$$Ax + By = C$$$. Что делается при помощи расширенного алгоритма Евклида. Подробно решение описываться не будет, так как оно не требует никаких выводов или дополнительных знаний, кроме знания самого алгоритма и его применения для диофантовых уравнений. Единственное, что требовалось кроме знания алгоритма — заметить, что вес дается без учета грифа, а значит информация про 20 кг была лишней $$$:)$$$

Псевдокод

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
ll gcd_ext (ll a,ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = gcd_ext(b,a%b,x,y);

    ll old_x = x;
    ll old_y = y;

    x = old_y;
    y = old_x - (a/b)*old_y;
    return d;
}
int main()
{
    ll a,b,c;
    cin>>a>>b>>c;
    bool swaped = 0;
    if (a<b)
    {
        swaped = 1;
        swap(a,b);
    }
    ll d = __gcd(a,b);
    if (c%d!=0)
    {
        cout<<"NO";
        return 0;
    }

    ll A = a/d;
    ll B = b/d;
    ll C = c/d;

    ll x,y;
    gcd_ext(A,B,x,y);
    x *=C;
    y *=C;
    if (swaped)
    {
        swap(a,b);
        swap(x,y);
        swap(A,B);
    }
   // cout<<x<<' '<<y<<'\n';
    if (x < 0)
    {
        ll k = (-x)/B;
        if ((-x)%B!=0)
        {
            ++k;
        }
        if (x + k*B >=0 && y -k*A>=0)
        {
            // cout<<x +k*B<<' '<<y - k*A<<'\n';
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
    }
    else
    {
        if (y<0)
        {
            ll k = (-y)/A;
            if ((-y)%A!=0)
            {
                ++k;
            }
            if (x - k*B >=0 && y +k*A>=0)
            {
              //  cout<<x -k*B<<' '<<y + k*A<<'\n';
                cout<<"YES\n";
            }
            else
            {
                cout<<"NO\n";
            }
        }
        else
        {
           // cout<<x<<' '<<y<<'\n';
            cout<<"YES\n";
        }
    }
}

G задача

Разбор

Автор задачи : MegaEnderman2009

В этой задаче вам нужно было сделать несколько важных выводов.

Первый вывод — количество чисел Фибоначчи растет логарифмически, а значит кол-во чисел Фибоначчи находящихся до числа $$$X$$$ можно считать как $$$log(X)$$$. Обозначим кол-во чисел Фибоначчи меньших длины исходного массива как $$$L$$$. Создадим двумерный массив $$$M$$$ размера $$$L$$$.

Второй вывод — Хоть кол-во чисел Фибоначчи, которые могут быть индексами массива мало ограничение в задаче на номер числа Фибоначчи -- $$$10^9$$$. Почему? В условии написано, что все берется в нуль-индексации, а значит, всегда есть хотя бы $$$1$$$ индекс $$$i$$$, такой что $$$i$$$ $$$mod$$$ $$$f_{f_{num}} = 0$$$, это всегда выполняется при $$$i = 0$$$. А значит для больших числе Фибоначчи достаточно просто увеличить первый элемент массива.

После того как мы сделали первый вывод мы могли завести $$$M$$$ массивов. Размер массива номер $$$i$$$ показывал бы, сколько раз в исходном массиве встречаются индексы кратные $$$f_i$$$. А каждый элемент массива $$$M_{i,j}$$$ отвечал бы за элемент $$$a_{j * f_i}$$$ исходного массива.

Для запросов второго типа, нам нужно лишь выбрать соответствующий массив $$$M_{f_{num}}$$$ и добавить $$$val$$$ на отрезке от $$$l$$$ до $$$r$$$. Для запросов первого типа нам нужно пройтись по массиву $$$M$$$ и для каждого $$$M_i$$$ найти его отрезок $$$[L:R]$$$ такой, что $$$l<=L*f_i<=R*f_i<=r$$$ и прибавить к ответу сумму на этом отрезке. Потом к получившемуся ответу добавим сумму на отрезке $$$[l:r]$$$ исходного массива и получим ответ на запрос. Теперь нам остается лишь использовать структуру данных, которая могла бы эффективно отвечать на запросы суммы и добавлять на отрезке. Например Дерево Отрезков , sqrt — декомпозиция.

Псевдокод 1

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ll = long long;
using namespace std;
struct SegmentTree
{

    vector <ll> tree;
    vector <ll> lazy;
    vector <ll> pos;
    void assignment(vector <ll> &a, ll fib)
    {
        ll n = a.size();
        ll lenpos = 0;
        for (int i = 0; i < n; i+=fib)
        {
            pos.push_back(i);
            lenpos++;

        }
        tree.resize(4 * lenpos + 1,0);
        lazy.resize(4 * lenpos + 1,0);
        return;
    }
    void build(ll tl,ll tr,ll v)
    {
        if (tl == tr)
        {
            tree[v] = 0;
            lazy[v] = 0;
            return;
        }
        ll mid = (tl + tr) >> 1;
        build(tl,mid,v * 2 + 1);
        build(mid + 1,tr,v * 2 + 2);
        tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }
    void push(ll tl,ll tr,ll v)
    {
        if (tl != tr && lazy[v] != 0)
        {
            ll mid = (tl + tr) >> 1;
            tree[v * 2 + 1] += (mid - tl + 1) * lazy[v];
            tree[v * 2 + 2] += (tr - mid) * lazy[v];
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
            lazy[v] = 0;
        }
    }
    void update(ll tl,ll tr,ll l,ll r,ll v,ll val)
    {
        if (l > r)
            return;
        if (tl == l && tr == r)
        {
            tree[v] += (tr - tl + 1) * val;
            lazy[v] += val;
            return;
        }
        push(tl,tr,v);
        ll mid = (tl + tr) >> 1;
        update(tl,mid,l,min(r,mid),v * 2 + 1,val);
        update(mid + 1,tr,max(l,mid + 1),r,v * 2 + 2,val);
        tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }
    ll get(ll tl,ll tr,ll l,ll r,ll v)
    {
        if (l > r)
            return 0;
        if (tl == l && tr == r)
            return tree[v];
        push(tl,tr,v);
        ll mid = (tl + tr) >> 1;
        ll left = get(tl,mid,l,min(r,mid),v * 2 + 1);
        ll right = get(mid + 1,tr,max(l,mid + 1),r,v * 2 + 2);
        return left + right;
    }
};
void Solve()
{
    ll n;
    cin >> n;

    vector <ll> fib(2,1);

    for (int i = 2; i < n ; i++)
    {
        ll sum = fib[i - 1] + fib[i - 2];
        fib.push_back(sum);
        if(sum > n)
            break;
    }
    ll lenFib = fib.size();


    vector <ll> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];


    vector <ll> pref(n + 1,0);
    for (int i = 0; i < n; i++)
        pref[i + 1] = pref[i] + a[i];


    SegmentTree f[lenFib];
    for (int i = 0; i < lenFib; ++i)
        f[i].assignment(a,fib[i]);

    ll q;
    cin >> q;
    while (q-->0)
    {
        ll type;
        cin >> type;
        if (type == 1)
        {
            ll l, r;
            cin >> l >> r;
            ll ans = pref[r + 1] - pref[l];
            for (int f_num = 0; f_num < lenFib; f_num++)
            {
                auto L = lower_bound(f[f_num].pos.begin(), f[f_num].pos.end(), l) - f[f_num].pos.begin();
                auto R = upper_bound(f[f_num].pos.begin() + L - 1, f[f_num].pos.end(), r) - f[f_num].pos.begin() - 1;

                if (L <= R)
                    ans += f[f_num].get(0,f[f_num].pos.size() - 1,L,R,0);
            }
            cout << ans << '\n';
        }
        else
        {
            ll f_num, l, r, val;
            cin >> f_num >> l >> r >> val;

            if (f_num >= lenFib)
            {
                if (l == 0)
                    f[0].update(0,f[0].pos.size() - 1,0,0,0,val);
                continue;
            }

            if (l >= f[f_num].pos.size())
                continue;


            r = min(r, (ll)(f[f_num].pos.size()) - 1);
            f[f_num].update(0,f[f_num].pos.size() - 1,l,r,0,val);
        }




    }
}
int main()
{
    // freopen("input.txt","r",stdin);
    //  freopen("output.txt","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    //  cin >> tt;
    while (tt-->0)
    {
        Solve();
        // cout << '\n';
    }
}

Псевдокод 2

#include <iostream>
#include <vector>
using ll = long long;
using namespace std;
class node
{
public:
	ll sum = 0;
	ll add = 0;
	node  operator + (node b)
	{
		node c;
		c.sum = this->sum + b.sum;
		return c;
	}

	node operator = (node b)
	{
		this->add = b.add;
		this->sum = b.sum;
		return *this;
	}

	node operator = (ll x)
	{
		this->sum = x;
		return *this;
	}


};
class SegmentTree
{
private:
	ll MaxLeafNumb;
	vector <node> tree;
	void build(vector<ll>& vec)
	{
		for (MaxLeafNumb=1; MaxLeafNumb < (ll)vec.size(); MaxLeafNumb *= 2);
		tree.resize(2 * MaxLeafNumb--);
	}
	node build(ll l, ll r, ll vertex, vector<ll>& vec)
	{
		if (l == r)
		{
			if (l >= vec.size())
			{
				return tree[vertex] = 0;
			}
			return tree[vertex] = vec[l];
		}
		ll mid = (l + r) / 2;
		return tree[vertex] = build(l, mid, vertex * 2 + 1, vec) + build(mid + 1, r, vertex * 2 + 2, vec);
	}


	void push(ll l, ll r, ll vertex)
	{
		if (l == r)
		{
			tree[vertex].sum += tree[vertex].add*(r-l+1);
			tree[vertex].add = 0;
		}
		else
		{
			tree[vertex * 2 + 1].add += tree[vertex].add;
			tree[vertex * 2 + 2].add += tree[vertex].add;
			tree[vertex].sum += tree[vertex].add * (r - l + 1);
			tree[vertex].add = 0;

		}
	}

	void Increase(ll L, ll R, ll l, ll r, ll vertex, ll val)
	{
		push(l, r, vertex);
		if (r < L || l>R)
		{
			return;
		}
		if (l >= L && r <= R)
		{
			tree[vertex].add += val;
			push(l, r, vertex);
			return;
		}
		ll mid = (l + r) / 2;
		Increase(L, R, l, mid, vertex * 2 + 1, val);
		Increase(L, R, mid + 1, r, vertex * 2 + 2, val);
		tree[vertex] = tree[vertex * 2 + 1] + tree[vertex * 2 + 2];
	}

	ll GetSum(ll L, ll R, ll l, ll r, ll vertex)
	{
		push(l, r, vertex);
		if (l > R || r < L)
		{
			return 0;
		}
		if (l >= L && r <= R)
		{
			return tree[vertex].sum;
		}
		ll mid = (r + l) / 2;
		return GetSum(L, R, l, mid, vertex * 2 + 1) + GetSum(L, R, mid + 1, r, vertex * 2 + 2);
	}
public:
	SegmentTree(vector<ll>& vec)
	{
		build(vec);
		build(0, MaxLeafNumb, 0, vec);
	}
	SegmentTree()
	{

	}
	void add(ll l, ll r, ll val)
	{
		Increase(l, r, 0, MaxLeafNumb, 0, val);
	}

	ll sum(ll l, ll r)
	{
		return (GetSum(l, r, 0, MaxLeafNumb, 0));
	}

};

pair<ll, ll> convert(ll l, ll r, ll val)
{
	if (l % val == 0)
	{
		return { l / val, r / val };
	}
	else
	{
		return { l / val + 1 , r / val };
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	vector<ll> vec(n);
	for (ll i = 0; i < n; ++i)
	{
		cin >> vec[i];
	}

	vector <ll> fibb(2, 1);
	for (ll i = 2; ; i++)
	{
		if (fibb[i - 1] + fibb[i - 2] > n)
		{
			break;
		}
		else
		{
			fibb.push_back(fibb[i - 1] + fibb[i - 2]);
		}
	}

	vector<vector<ll>> matrix;

	for (ll i = 0; i < fibb.size(); ++i)
	{
		vector<ll> temp;
		for (ll j = 0; j < n; ++j)
		{
			if (j % fibb[i] == 0)
			{
				temp.push_back(0);
			}
		}
		matrix.push_back(temp);
	}

	vector<SegmentTree> forest(matrix.size());

	for (ll i = 0; i < forest.size(); ++i)
	{
		SegmentTree tree(matrix[i]);

		forest[i] = tree;
	}



	ll q;
	cin >> q;
	ll over_size_add = 0;

	vector<ll> pref(n + 1, 0);
	for (ll i = 1; i <= n; ++i)
	{
		pref[i] = vec[i - 1] + pref[i - 1];
	}

	while (q--)
	{
		ll operation_type;
		cin >> operation_type;
		if (operation_type == 2)
		{
			ll f_num, l, r, val;
			cin >> f_num >> l >> r >> val;
			if (f_num >= forest.size())
			{
				over_size_add += val;
				continue;
			}
			forest[f_num].add(l, r, val);
		}
		else
		{
			ll l, r;
			cin >> l >> r;
			ll res = 0;
			if (l == 0)
			{
				res += over_size_add;
			}
			for (ll i = 0; i < fibb.size(); ++i)
			{
				pair<ll, ll> temp = convert(l, r, fibb[i]);
				ll temp_l = temp.first ;
				ll temp_r = temp.second ;
				if (temp_r < temp_l)
				{
					continue;
				}
				res += forest[i].sum(temp_l, temp_r);
			}
			cout <<pref[r + 1] - pref[l] + res << '\n';
		}

	}
}

Оценки задачам

Оценки