This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3024 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../segtree/persistent/ushi.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; vector<int> as(n),bs(n); for(int i=0;i<n;i++) cin>>as[i]; for(int i=0;i<n;i++) cin>>bs[i]; auto f=[](int a,int b){return min(a,b);}; int ti=INT_MAX; SegmentTree<int> seg(f,ti); auto ra=seg.build(as); auto rb=seg.build(bs); int q; cin>>q; for(int i=0;i<q;i++){ int x,y,z; cin>>x>>y>>z; y--; if(x==1) ra=seg.set_val(ra,y,z); if(x==2) rb=seg.set_val(rb,y,z); if(x==3) cout<<seg.query(ra,y,z)<<"\n"; if(x==4) cout<<seg.query(rb,y,z)<<"\n"; if(x==5) ra=seg.clone(rb); if(x==6) rb=seg.clone(ra); } cout<<flush; return 0; }
#line 1 "test/aoj/3024.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3024 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "segtree/persistent/ushi.cpp" #line 3 "segtree/persistent/ushi.cpp" using namespace std; #endif //BEGIN CUT HERE template <typename T> struct SegmentTree{ using F = function<T(T,T)>; F f; T ti; SegmentTree(F f,T ti):f(f),ti(ti){} struct Node{ Node *l,*r; T dat; Node(T dat):dat(dat){l=r=nullptr;} }; Node* clone(Node *a){ return new Node(*a); } Node* reflect(Node *a){ a->dat=f(a->l->dat,a->r->dat); return a; } int n,height; Node* build(const vector<T> &v){ int n_=v.size(); n=1;height=0; while(n<n_) n<<=1,height++; vector<Node*> vs(n<<1); for(int i=0;i<n_;i++) vs[n+i]=new Node(v[i]); for(int i=n_;i<n;i++) vs[n+i]=new Node(ti); for(int i=n-1;i;i--){ vs[i]=new Node(ti); vs[i]->l=vs[(i<<1)|0]; vs[i]->r=vs[(i<<1)|1]; reflect(vs[i]); } return vs[1]; } Node* set_val(Node* t,int k,T x,int h){ t=clone(t); if(h<0){ t->dat=x; return t; } if((k>>h)&1) t->r=set_val(t->r,k,x,h-1); else t->l=set_val(t->l,k,x,h-1); return reflect(t); } T query(Node* t,int l,int r,int lb,int ub){ if(r<=lb or ub<=l) return ti; if(l<=lb and ub<=r) return t->dat; int m=(lb+ub)>>1; return f(query(t->l,l,r,lb,m),query(t->r,l,r,m,ub)); } Node* set_val(Node* t,int k,T x){ return set_val(t,k,x,height-1); } T query(Node* t,int l,int r){ return query(t,l,r,0,n); } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 8 "test/aoj/3024.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; vector<int> as(n),bs(n); for(int i=0;i<n;i++) cin>>as[i]; for(int i=0;i<n;i++) cin>>bs[i]; auto f=[](int a,int b){return min(a,b);}; int ti=INT_MAX; SegmentTree<int> seg(f,ti); auto ra=seg.build(as); auto rb=seg.build(bs); int q; cin>>q; for(int i=0;i<q;i++){ int x,y,z; cin>>x>>y>>z; y--; if(x==1) ra=seg.set_val(ra,y,z); if(x==2) rb=seg.set_val(rb,y,z); if(x==3) cout<<seg.query(ra,y,z)<<"\n"; if(x==4) cout<<seg.query(rb,y,z)<<"\n"; if(x==5) ra=seg.clone(rb); if(x==6) rb=seg.clone(ra); } cout<<flush; return 0; }