Branch Manger - INFSYS

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#ifdef  ONLINE_JUDGE
    #define eprintf(...) 42
#else
        #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#endif
clock_t startTime;
double getCurrentTime()
{
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}



const int SZ = 131072;
int seg_mini[2*SZ], seg_maxi[2*SZ];
set<int> indi[100005];

long long combine_mini(long long a, long long b)
{
    return min(a, b);
}
int update_mini(int p, int value)
{
    p += SZ;
    seg_mini[p] = value;
    for (; p > 1; p >>= 1)
    {
            seg_mini[p>>1] = combine_mini(seg_mini[(p|1)^1], seg_mini[p|1]);
    }
    return 0;
}
long long query_mini(int l, int r)
{
    long long resL = 2e9, resR = 2e9; r++;
    for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
        if (l&1) resL = combine_mini(resL,seg_mini[l++]);
        if (r&1) resR = combine_mini(seg_mini[--r],resR);
    }
    return combine_mini(resL,resR);
}

long long combine_maxi(long long a, long long b)
{
    return max(a, b);
}
int update_maxi(int p, int value)
{
    p += SZ;
    seg_maxi[p] = value;
    for (; p > 1; p >>= 1)
    {
            seg_maxi[p>>1] = combine_maxi(seg_maxi[(p|1)^1], seg_maxi[p|1]);
    }
    return 0;
}
long long query_maxi(int l, int r)
{
    long long resL = -2e9, resR = -2e9; r++;
    for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
        if (l&1) resL = combine_maxi(resL,seg_maxi[l++]);
        if (r&1) resR = combine_maxi(seg_maxi[--r],resR);
    }
    return combine_maxi(resL,resR);
}

int check(int l, int r, int len)
{
    int maxi = query_maxi(l, r);
    int mini = query_mini(l, r);
    return (maxi-mini+1)<=len;
}
int calculate_ans(int n, int q, vector<int> A, vector<int> T, vector<int> X, vector<int> Y)
{
    long long ans = 0;
    for(int i=0; i<n; i++)
    {
        indi[A[i]].insert(i);
    }
    for(int i=0; i<=n; i++)
    {
        if(indi[i].empty())
        {
            update_mini(i, 1e9);
            update_maxi(i, -1e9);
        }
        else
        {
            update_mini(i, *indi[i].begin());
            update_maxi(i, *prev(indi[i].end()));
        }
    }
    for(int i=0; i<q; i++)
    {
        if(T[i]==1)
        {
            X[i]--;
            indi[A[X[i]]].erase(X[i]);
            if(indi[A[X[i]]].empty())
            {
                update_mini(A[X[i]], 1e9);
                update_maxi(A[X[i]], -1e9);
            }
            else
            {
                update_mini(A[X[i]], *indi[A[X[i]]].begin());
                update_maxi(A[X[i]], *prev(indi[A[X[i]]].end()));

            }
            indi[Y[i]].insert(X[i]);
            update_mini(Y[i], *indi[Y[i]].begin());
            update_maxi(Y[i], *prev(indi[Y[i]].end()));
            A[X[i]] = Y[i];
        }
        else
        {
            int l = X[i], r = n+1;
            while(l<r)
            {
                int mid = l + (r-l)/2;

                if(check(X[i], mid, Y[i]))
                {
                    l = mid+1;
                }
                else
                {
                    r = mid;
                }
            }
            ans ^= l-X[i];
        }
    }
    return ans;
}





int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    startTime = clock();
    while(t--)
    {
        int n, q;
        cin>>n>>q;
        vector<int> A(n), T(q), X(q), Y(q);
        for(int i=0; i<n; i++)
        {
            cin>>A[i];
        }
        for(int i=0; i<q; i++)
        {
            cin>>T[i];
        }
                for(int i=0; i<q; i++)
        {
            cin>>X[i];
        }
                for(int i=0; i<q; i++)
        {
            cin>>Y[i];
        }
        cout<<calculate_ans(n, q, A, T, X, Y)<<endl;
    }
    eprintf("time = %.5lf\n", getCurrentTime());
    return 0;
}