Submission #650400

#	Time	Username	Problem	Language	Result	Execution time	Memory
650400		sofija6	Addk (eJOI21_addk)	C++14	0 / 100	120 ms	7152 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
using namespace std;
ll n,a[MAXN],m,p[20],v[20];
struct element
{
    ll s=0,sl=0,sr=0,cnt=0;
};
struct seg_tree
{
    vector<element> st;
    element neutral_element;
    element Merge(element x,element y)
    {
        element z;
        z.s=x.s+y.s;
        z.sl=x.sl+y.sl+y.s*x.cnt;
        z.sr=y.sr+x.sr+x.s*y.cnt;
        z.cnt=x.cnt+y.cnt;
        return z;
    }
    void Init()
    {
        m=1;
        while (m<n)
            m <<= 1;
        st.resize(2*m,neutral_element);
    }
    void Build()
    {
        for (ll i=m;i<m+n;i++)
            st[i]={a[i-m+1],a[i-m+1],a[i-m+1],1};
        for (ll i=m-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    void Add(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (rx<pos || lx>pos)
            return;
        if (rx==lx)
        {
            st[x]={val,val,val,1};
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Add(pos,val,2*x,lx,mid);
        else
            Add(pos,val,2*x+1,mid+1,rx);
        st[x]=Merge(st[2*x],st[2*x+1]);
    }
    element Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (rx<l || lx>r)
            return neutral_element;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll k,q,t;
    cin >> n >> k;
    for (ll i=1;i<=n;i++)
        cin >> a[i];
    S.Init();
    S.Build();
    cin >> q;
    while (q--)
    {
        cin >> t;
        if (t==1)
        {
            for (ll i=1;i<=k;i++)
            {
                cin >> p[i];
                v[i]=a[p[i]];
            }
            for (ll i=1;i<k;i++)
            {
                a[p[i]]=v[i+1];
                S.Add(p[i],v[i+1],1,1,m);
            }
            a[p[k]]=v[1];
            S.Add(p[k],v[1],1,1,m);
            continue;
        }
        ll l,r,len;
        cin >> l >> r >> len;
        ll x,y,z;
        if (r-l+1>=2*len)
        {
            x=S.Calc(l,l+len-1,1,1,m).sl;
            y=len*S.Calc(l+len,r-len,1,1,m).s;
            z=S.Calc(r-len+1,r,1,1,m).sr;
        }
        else
        {
            ll d=r-len;
            x=S.Calc(l,d,1,1,m).sl;
            y=d*S.Calc(d+1,r-d,1,1,m).s;
            z=S.Calc(r-d+1,r,1,1,m).sr;
        }
        cout << x+y+z << "\n";
    }
    return 0;
}

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