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=0425 #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../algorithm/mo.cpp" #include "../../vector/identity.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,k,q; cin>>n>>k>>q; vector<int> as(k),bs(k); for(int i=0;i<k;i++) cin>>as[i]>>bs[i],as[i]--,bs[i]--; vector<int> ord=identity(n); vector<int> pos=identity(n); auto moveL= [&](int i){ int x=pos[as[i]],y=pos[bs[i]]; swap(ord[x],ord[y]); swap(pos[ord[x]],pos[ord[y]]); }; auto moveR= [&](int i){ int x=as[i],y=bs[i]; swap(ord[x],ord[y]); swap(pos[ord[x]],pos[ord[y]]); }; Mo mo(q,400,moveL,moveR,moveL,moveR); vector<int> qs(q),ls(q),rs(q),xs(q); for(int i=0;i<q;i++){ cin>>qs[i]>>ls[i]>>rs[i]>>xs[i]; ls[i]--;xs[i]--; mo.add(ls[i],rs[i]); } mo.build(); vector<int> ans(q,-1); for(int i=0;i<q;i++){ int p=mo.process(); if(qs[p]==1) ans[p]=ord[xs[p]]+1; if(qs[p]==2) ans[p]=pos[xs[p]]+1; } for(int a:ans) cout<<a<<"\n"; cout<<flush; return 0; }
#line 1 "test/aoj/0425.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0425 #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "algorithm/mo.cpp" #line 3 "algorithm/mo.cpp" using namespace std; #endif //BEGIN CUT HERE struct Mo{ using F = function<void(int)>; vector<int> ls,rs,ord; int n,width,nl,nr,ptr; F expandL,expandR; F shrinkL,shrinkR; Mo(int n,int width,F expandL,F expandR,F shrinkL,F shrinkR): n(n),width(width),nl(0),nr(0),ptr(0), expandL(expandL),expandR(expandR), shrinkL(shrinkL),shrinkR(shrinkR){} Mo(int n,int width,F expand,F shrink): Mo(n,width,expand,expand,shrink,shrink){} void add(int l,int r){ ls.emplace_back(l); rs.emplace_back(r); } void build(){ ord.resize(ls.size()); iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(), [&](int a,int b){ if(ls[a]/width!=ls[b]/width) return ls[a]<ls[b]; if(rs[a]==rs[b]) return ls[a]<ls[b]; return bool((rs[a]<rs[b])^((ls[a]/width)&1)); }); } int process(){ if(ptr==(int)ord.size()) return -1; const int idx=ord[ptr++]; while(nl>ls[idx]) expandL(--nl); while(nr<rs[idx]) expandR(nr++); while(nl<ls[idx]) shrinkL(nl++); while(nr>rs[idx]) shrinkR(--nr); return idx; } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "vector/identity.cpp" #line 3 "vector/identity.cpp" using namespace std; #endif //BEGIN CUT HERE vector<int> identity(int n){ vector<int> ord(n); iota(ord.begin(),ord.end(),0); return ord; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 9 "test/aoj/0425.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,k,q; cin>>n>>k>>q; vector<int> as(k),bs(k); for(int i=0;i<k;i++) cin>>as[i]>>bs[i],as[i]--,bs[i]--; vector<int> ord=identity(n); vector<int> pos=identity(n); auto moveL= [&](int i){ int x=pos[as[i]],y=pos[bs[i]]; swap(ord[x],ord[y]); swap(pos[ord[x]],pos[ord[y]]); }; auto moveR= [&](int i){ int x=as[i],y=bs[i]; swap(ord[x],ord[y]); swap(pos[ord[x]],pos[ord[y]]); }; Mo mo(q,400,moveL,moveR,moveL,moveR); vector<int> qs(q),ls(q),rs(q),xs(q); for(int i=0;i<q;i++){ cin>>qs[i]>>ls[i]>>rs[i]>>xs[i]; ls[i]--;xs[i]--; mo.add(ls[i],rs[i]); } mo.build(); vector<int> ans(q,-1); for(int i=0;i<q;i++){ int p=mo.process(); if(qs[p]==1) ans[p]=ord[xs[p]]+1; if(qs[p]==2) ans[p]=pos[xs[p]]+1; } for(int a:ans) cout<<a<<"\n"; cout<<flush; return 0; }