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_B" #include "../template.hpp" #include "../DataStructure/BinaryTrie.hpp" signed main(){ BinaryTrie<int,18> trie; int n,q;cin>>n>>q; while(q--){ int c,x,y;cin>>c>>x>>y; if(c==0) trie.add(x,y); else cout<<trie.count_less(y+1)-trie.count_less(x)<<endl; } return 0; }
#line 1 "test/AOJ_DSL_2_B.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B" #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_B.test.cpp" #line 1 "DataStructure/BinaryTrie.hpp" template<typename BitType,int MAXLOG,typename C=int> struct BinaryTrie{ private: struct Node{ Node *nxt[2]; C cnt; Node():nxt{nullptr,nullptr},cnt(0){} }; Node *root; Node *find(BitType bit,BitType xor_val=0){ Node *cur=root; for(int i=MAXLOG-1;i>=0;i--){ bool target=(xor_val>>i)&1; bool go_to=target^((bit>>i)&1); if(!cur->nxt[go_to]) return nullptr; cur=cur->nxt[go_to]; } return cur; } public: BinaryTrie():root(new Node()){} void add(BitType bit,C c=1,BitType xor_val=0){ Node *cur=root; for(int i=MAXLOG-1;i>=0;i--){ bool target=(xor_val>>i)&1; bool go_to=target^((bit>>i)&1); if(!cur->nxt[go_to]) cur->nxt[go_to]=new Node(); cur->cnt+=c; cur=cur->nxt[go_to]; } cur->cnt+=c; return ; } void erase(BitType bit,C c=1,BitType xor_val=0){ add(bit,-c,xor_val); } BitType kth_element(C k,BitType xor_val=0){ assert(0<=k and k<root->cnt); C ret=0; Node *cur=root; for(int i=MAXLOG-1;i>=0;i--){ bool xored_0=(xor_val>>i)&1; if(!cur->nxt[xored_0] or cur->nxt[xored_0]->cnt<=k){ k-=(cur->nxt[xored_0]?cur->nxt[xored_0]->cnt:0); cur=cur->nxt[xored_0^1]; ret+=(BitType(1)<<i); }else{ cur=cur->nxt[xored_0]; } } return ret; } BitType min_element(BitType xor_val=0){ return kth_element(0,xor_val); } BitType max_element(BitType xor_val=0){ return kth_element(root->cnt-1,xor_val); } C count(BitType bit,BitType xor_val=0){ auto target=find(bit,xor_val); return target?target->cnt:0; } C count_less(BitType bit,BitType xor_val=0){ C ret=0; Node *cur=root; for(int i=MAXLOG-1;i>=0;i--){ if(!cur) break; bool xored_0=(xor_val>>i)&1; if((bit>>i)&1 and cur->nxt[xored_0]) ret+=cur->nxt[xored_0]->cnt; cur=cur->nxt[xored_0^((bit>>i)&1)]; } return ret; } }; #line 6 "test/AOJ_DSL_2_B.test.cpp" signed main(){ BinaryTrie<int,18> trie; int n,q;cin>>n>>q; while(q--){ int c,x,y;cin>>c>>x>>y; if(c==0) trie.add(x,y); else cout<<trie.count_less(y+1)-trie.count_less(x)<<endl; } return 0; }