Submission #1198246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198246		AzeTurk810	Addk (eJOI21_addk)	C++20	100 / 100	139 ms	11592 KiB

Main

// Telebe of adicto yani AzeTurk810
//
// WHY ARE YOU STARING MY CODE Stranger ??!!
//
//GO AWAY AND DON T look my CODE if i don t know you or you are stalker !!!!(hrrr)
//
// here about me: I am alone of course, fun , ' , ' , love pyhcics , young(child) , love music , had birds , not a gamer , chess :) , dead to football , you are looking to code , ... ;
//
// why at 1 japon army march they say "the enemy geniral is a hero , an equal to no one. Both in glory and in victory
// the men that follow him are also brave , fearless wariors ..."?(brave sozu feedback lere gore duzeldilmisdir)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

# define ln '\n'
# define INFi 1e9
# define INFll 1e18
# define MOD int(1e9 + 7)

struct node
{
    ll az , nor , cox;
};

node c(node &l , node &r , ll sizel , ll sizer) {
    return {l.az + l.nor * sizer + r.az , l.nor + r.nor , l.cox + r.cox + sizel * r.nor};
}

int xl , xr;

struct segTree
{
    vector<node> t;
    segTree(int n) {
        t.resize(n * 4);
    }
    void build(int v , int l , int r , vector<int> &a) {
        if(l == r) {
            t[v].nor = a[l];
            t[v].az = a[l];
            t[v].cox = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build((v << 1) , l , mid , a);
        build((v << 1)|1 , mid + 1 , r , a);
        t[v] = c(t[(v << 1)] , t[(v<<1)|1] , mid - l + 1 ,r - mid);
    }
    void upd(int v , int l , int r , int pos , int val) {
        // cerr << l << '|'<< r << endl;
        if(l == r) {
            t[v].nor = val;
            t[v].az = val;
            t[v].cox = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(mid >= pos)upd((v << 1) , l , mid , pos , val);
        else upd((v << 1)|1 , mid + 1 , r , pos , val);
        t[v] = c(t[(v << 1)] , t[(v<<1)|1] , mid - l + 1 ,r - mid);
    }
    ll ask(int v , int l , int r , int ql , int qr , int m) {
        if(ql > r || qr < l) return 0;
        // cerr << l << ' ' << r << ' ' << xl << ' ' << xr << ' ' << t[v].cox << ' ' << t[v].nor << ' ' << t[v].az << endl;
        if(ql <= l && r <= qr) {
            if(qr - ql + 1 == m)return t[v].nor;
            if((xl<= l && r <= xr)) {
                // cout << l << '|' << r<< ' ' << t[v].nor * (xl - ql + 1) << endl;
                return t[v].nor * (xl - ql + 1);
            }
            if(r <= xl) {
                // cout << l << ':' << r<< ' ' << t[v].cox + (l - ql) * t[v].nor << endl;
                return t[v].cox + (l - ql) * t[v].nor;
            }
            if(xr <= l) {
                // cout << l << ':' << r<< ' ' << t[v].az + (qr - r) * t[v].nor << endl;
                return t[v].az + (qr - r) * t[v].nor;
            }
        }
        int mid = (l + r) >> 1;
        return ask((v << 1) , l , mid , ql , qr , m) + ask((v << 1) | 1 , mid + 1 , r , ql , qr , m);
    }
};

void siw(vector<int> &a , vector<int> &w , segTree &t) {
    int ff = a[w[0]];
    vector<int> nums;
    for(int i : w) {
        nums.push_back(a[i]);
    }
    for(int i = 1; i < w.size() ; i ++) {
        a[w[i- 1]] = nums[i];
        t.upd(1 , 0 , a.size() - 1 , w[i - 1] , nums[i]);
    }
    a[w[w.size() - 1]] = ff;
    t.upd(1 , 0 , a.size() - 1 , w.back() , ff);
}

void solve() {
    int n , k;
    cin >> n >> k;
    vector<int> a(n);
    for(int &i : a) cin >> i;
    segTree t(n);
    t.build(1 , 0 , n - 1, a);
    int q;
    vector<int> sw(k);
    cin >> q;
    while(q--) {
        int tt;
        cin >> tt;
        if(tt == 1) {
            for(int i = 0 ; i < k ; i ++) {
                cin >> sw[i];
                sw[i]--;
            }
            siw(a , sw , t); 
        } else {
            int l , r , m;
            cin >> l >> r >> m;
            l--;r--;
            xl = l + m - 1;
            xr = r - m + 1;
            if(xl > xr)swap(xl , xr);
            cout << t.ask(1 , 0 , n - 1 , l , r , m) << ln;
        }
    } 
    // for(int i = 0; i <n ; i ++) {
    //     cerr << a[i] << ' ';
    // }
} 


signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--)solve();
}
/*
5 1
1 2 3 4 5
3 
2 1 2 1
2 1 2 2
2 1 3 1


Test: 2 ci dehvdir , 6 vermelidir 5 verir , niye? , sehv basarliyla onarildi
3 cu sehv verir , 3 vermelidir , 6 verir , sehv onarildi
4 cu duzdur.
5 1
1 1 1 1 1
4
2 1 5 1
2 1 4 2
2 1 3 3
2 1 2 2

kod sehv verdi , yeni tsk:abort
8 4
1 1 1 2 1 1 1 1
10
2 1 8 7
2 1 8 6
1 2 3 4 5
2 1 8 7
2 1 8 6
2 3 3 1
2 1 5 3
2 1 8 3
2 1 8 2
2 3 8 2
cavab:
16
21
16
21
2
12
21
16
11
cixis:abort
24
24
23
23
2
12
21
16
11
*/

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8