This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A" #include "../template.hpp" #include "../DataStructure/BinaryTrieMonoid.hpp" signed main(){ int n,q;cin>>n>>q; BinaryTrieMonoid<int,18,ll> trie([&](ll a,ll b){return (a<b?a:b);},(1ll<<31)-1); while(q--){ int c;ll x,y;cin>>c>>x>>y; if(c==0) trie.update(x,y); if(c==1) cout<<trie.query(x,y+1)<<endl; } return 0; }
#line 1 "test/AOJ_DSL_2_A.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/AOJ_DSL_2_A.test.cpp" #line 1 "DataStructure/BinaryTrieMonoid.hpp" template<typename BitType,int MAXLOG,typename Monoid> struct BinaryTrieMonoid{ private: struct Node{ Node *nxt[2]; Monoid val; Node(Monoid val):nxt{nullptr,nullptr},val(val){} }; Node *root; using F=function<Monoid(Monoid,Monoid)>; F f; const Monoid e; Monoid query(BitType a,BitType b,Node *cur,BitType l,BitType r,int dep,BitType xor_val){ if(a<=l and r<=b) return (cur?cur->val:e); if(dep<0 or b<=l or r<=a or !cur) return e; bool x0=(xor_val>>dep)&1; Monoid L=query(a,b,cur->nxt[x0],l,(l+r)/2,dep-1,xor_val); Monoid R=query(a,b,cur->nxt[x0^1],(l+r)/2,r,dep-1,xor_val); return f(L,R); } void update(Node *cur,Monoid x,BitType bit,int dep){ if(dep==-1){ cur->val=x; return ; } bool go_to=(bit>>dep)&1; if(!cur->nxt[go_to]) cur->nxt[go_to]=new Node(e); update(cur->nxt[go_to],x,bit,dep-1); cur->val=f(cur->nxt[0]?cur->nxt[0]->val:e,cur->nxt[1]?cur->nxt[1]->val:e); return ; } public: BinaryTrieMonoid(F f,const Monoid &e):root(new Node(e)),f(f),e(e){} // fold [l,r) // xor_valを指定したとき,可換じゃない演算だと壊れると思います.多分 Monoid query(BitType l,BitType r,BitType xor_val=0){ return query(l,r,root,0,BitType(1)<<MAXLOG,MAXLOG-1,xor_val); } void update(BitType bit,Monoid x){ update(root,x,bit,MAXLOG-1); } Monoid operator[](const BitType &k){ return query(k,k+1); } }; #line 6 "test/AOJ_DSL_2_A.test.cpp" signed main(){ int n,q;cin>>n>>q; BinaryTrieMonoid<int,18,ll> trie([&](ll a,ll b){return (a<b?a:b);},(1ll<<31)-1); while(q--){ int c;ll x,y;cin>>c>>x>>y; if(c==0) trie.update(x,y); if(c==1) cout<<trie.query(x,y+1)<<endl; } return 0; }