Submission #1027113

#TimeUsernameProblemLanguageResultExecution timeMemory
1027113Dennis_JasonXORanges (eJOI19_xoranges)C++14
100 / 100
411 ms13500 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...