This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
//#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 5001
#define nl '\n'
#define INF 0x3f3f3f3
#define pii1 pair<int, pair<int,int>> (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
vector<int>v;
class segtree{
private:
int n;
vector<int>treeI;
vector<int>treeP;
public:
void init(int sz)
{
n=sz;
treeI.resize(4*sz+1);
treeP.resize(4*sz+1);
}
int calc(int a,int b)
{
return a^b;
}
void build(int node,int st,int dr,vector<int>&v)
{
if(st==dr)
{
if(st%2==1)
{
treeI[node]=v[st];
treeP[node]=0;
}
else
{
treeI[node]=0;
treeP[node]=v[st];
}
return;
}
int mid=(st+dr)/2;
build(2*node,st,mid,v);
build(2*node+1,mid+1,dr,v);
treeI[node]=calc(treeI[2*node],treeI[2*node+1]);
treeP[node]=calc(treeP[2*node],treeP[2*node+1]);
}
void update(int node,int st,int dr,int pos,int val)
{
if(st==dr)
{
if(st%2==1)
{
treeI[node]=val;
treeP[node]=0;
}
else
{
treeI[node]=0;
treeP[node]=val;
}
return;
}
int mid=(st+dr)/2;
if(pos<=mid)
update(2*node,st,mid,pos,val);
else
update(2*node+1,mid+1,dr,pos,val);
treeI[node]=calc(treeI[2*node],treeI[2*node+1]);
treeP[node]=calc(treeP[2*node],treeP[2*node+1]);
}
int query_I(int node,int st,int dr,int L,int R)
{
if(R<st|| dr<L)
return 0;
if(L<=st && dr<=R)
{
return treeI[node];
}
int mid=(st+dr)/2;
int left=query_I(2*node,st,mid,L,R);
int right=query_I(2*node+1,mid+1,dr,L,R);
return left^right;
}
int query_P(int node,int st,int dr,int L,int R)
{
if(R<st|| dr<L)
return 0;
if(L<=st && dr<=R)
{
return treeP[node];
}
int mid=(st+dr)/2;
int left=query_P(2*node,st,mid,L,R);
int right=query_P(2*node+1,mid+1,dr,L,R);
return left^right;
}
int query(int L,int R)
{
if(L%2==1)
return query_I(1,1,n,L,R);
else
return query_P(1,1,n,L,R);
}
void build(vector<int>&v)
{
build(1,1,n,v);
}
void update(int pos,int val)
{
update(1,1,n,pos,val);
}
void check()
{
cout<<treeI[2]<<nl;
}
};
/*
* 1 2 3 4 5 6
* 1 2 2 3 3 4 4 5 5 6
* v[l]^v[r]^query(l,r)/false
*
* l,r
* 1 4
* 4 elemt de 1(r-l+1) = 1^2^3^4
* 3 elem de 2(r-l) = 1^2^2^3^3^4=1^4 ,(x^x=0),(x^0=x)
* 2 elem de3(r-l-1) = 1^2^3^2^3^4=1^2^2^3^3^4= 1^4
* 1 elem de 4(r-l-2) =1^2^3^4
* ans=1^1^1^1^2^2^3^3^4^4^4^4=0
* if(r-l+1)%2==0 is 0?x
*
* 1 3
* 3 elem de 1=1^2^3
* 2 elem de 2=1^2^2^3=1^3
* 1 elem de 3=1^2^3
* ans=1^1^1^2^2^3^3^3=1^3;
* 1*3,2*2,3*3
*
*
* v
* 3 2 3 4 5
* 1 5
* 5 elem de 1=3 ^ 2 ^ 3 ^ 4 ^ 5=3^2^4^5
* 4 elem de 2=3^2 ^ 2^3 ^ 3^4 ^ 4^5=3^5
* 3 elem de 3=3^2^3 ^ 2^3^4 ^ 3^4^5=5
* 2 elem de 4= 3^2^3^4 ^ 2^3^4^5%=3^5
* 1 elem de 5=3^2^3^4^5=2^4^5
* ans=2^2^3^3^5^5^5^5^5=5
5 elemente:1*5,2*8,3*9,4*8,5*5
3^3^5=5;
6 elem
*
* 123456
* 123 456
* 12 3 45 6
* 1 2 4 5
* if(ind%2==1) will count
* else no
*
*/
segtree st;
signed main() {
int n,q;
cin>>n>>q;
v.resize(n+1);
st.init(n);
for(int i=1;i<=n;++i)
{
cin>>v[i];
}
st.build(v);
for(int i=1;i<=q;++i)
{
int type;
cin>>type;
if(type==1)
{
int pos,val;
cin>>pos>>val;
st.update(pos,val);
}
else
{
int l,r;
cin>>l>>r;
if((r-l+1)%2==0)
{
cout<<0<<nl;
}
else
{
cout<<st.query(l,r)<<nl;
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |