제출 #650716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650716		sofija6	XORanges (eJOI19_xoranges)	C++14	100 / 100	160 ms	20304 KiB

xoranges

#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
ll n,a[MAXN],m;
struct element
{
   ll even=0,odd=0,cnt=0;
};
struct seg_tree
{
    vector<element> st;
    element neutral_element;
    element Merge(element x,element y)
    {
        element z;
        z=x;
        z.cnt+=y.cnt;
        if (x.cnt&1)
        {
            z.even^=y.odd;
            z.odd^=y.even;
        }
        else
        {
            z.even^=y.even;
            z.odd^=y.odd;
        }
        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]={0,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 (lx==rx)
        {
            st[x]={0,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 (lx>r || rx<l)
            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 q,t,l,r;
    cin >> n >> q;
    for (ll i=1;i<=n;i++)
        cin >> a[i];
    S.Init();
    S.Build();
    while (q--)
    {
        cin >> t >> l >> r;
        if (t==1)
            S.Add(l,r,1,1,m);
        else
        {
            if ((r-l+1)&1)
                cout << S.Calc(l,r,1,1,m).odd << "\n";
            else
                cout << "0\n";
        }
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25