fork download
copy 
  1. /// Day Created: mar 30th 2026
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. #define fname ""
  6. #define ll long long
  7.  
  8. using namespace std;
  9. int q;
  10.  
  11. int trie[2*100000*31+5][2], peaks=1;
  12. int c[2*100000*31+5];
  13. ll s[2*100000*31+5];
  14.  
  15. bool bit(int x, int i) {
  16. 	return (x>>i)&1;
  17. }
  18.  
  19. bool Exist(const int &x) {
  20. 	int u=1;
  21. 	for(int i=31; i>=0; --i) {
  22. 		bool b=bit(x, i);
  23. 		if(!trie[u][i] || c[trie[u][i]]==0) return 0;
  24. 		u=trie[u][i];
  25. 	}
  26. 	return 1;
  27. }
  28.  
  29. void idk() {return;}
  30.  
  31. void update(const int &x, const int &val, const int &add) {
  32. 	int u=1;
  33. 	s[u]+=val, c[u]+=add;
  34. 	for(int i=31; i>=0; --i) {
  35. 		bool b=bit(x, i);
  36. 		if(!trie[u][i]) trie[u][i]=++peaks;
  37. 		u=trie[u][i], s[u]+=val, c[u]+=add;
  38. 	}
  39. }
  40.  
  41. ll get(const int &x) { // sum of elements which is <x
  42. 	ll res=0;
  43. 	int u=1;
  44. 	for(int i=31; i>=0; --i) {
  45. 		bool b=bit(x, i);
  46. 		if(b) res+=s[trie[u][0]];
  47. 		if(!trie[u][b]) break;
  48. 		u=trie[u][b];
  49. 	}
  50. 	return res;
  51. }
  52.  
  53. int k_th(int x) {
  54. 	int res=0, u=1;
  55. 	for(int i=31; i>=0; --i) {
  56. 		if(c[trie[u][0]]<x) x-=c[trie[u][0]], res+=(1<<i), u=trie[u][1];
  57. 		else u=trie[u][0];
  58. 	}
  59. 	return res;
  60. }
  61.  
  62. int max_xor(int x) {
  63. 	int res=0, u=1;
  64. 	for(int i=31; i>=0; --i) {
  65. 		bool b=bit(x, i)^1;
  66. 		if(c[trie[u][b]]>0) res+=(b==1?(1<<i):0), u=trie[u][b];
  67. 		else b^=1, res+=(b==1?(1<<i):0), u=trie[u][b];
  68. 	}
  69. 	return res;
  70. }
  71. void solve() {
  72. 	cin>>q;
  73. 	while(q--) {
  74. 		int t;
  75. 		cin>>t;
  76. 		if(t!=3) {
  77. 			int x;
  78. 			cin>>x; 
  79. 			if(t==1) update(x, x, 1);
  80. 			if(t==2) Exist(x)?update(x, -x, -1):idk();
  81. 			if(t==4) cout<<k_th(x)<<'\n';
  82. 			if(t==5) cout<<max_xor(x)<<'\n';
  83. 		}
  84. 		else {
  85. 			int l, r;
  86. 			cin>>l>>r;
  87. 			cout<<get(r+1)-get(l)<<'\n';
  88. 		}
  89. 	}
  90. }
  91.  
  92. main() {
  93. 	if(fopen(fname".inp", "r")) {
  94. 		freopen(fname".inp", "r", stdin);
  95. 		freopen(fname".out", "w", stdout);
  96. 	}
  97. 	cin.tie(0)->sync_with_stdio(0);
  98. 	int tc=1;
  99. 	// cin>>tc;
  100. 	while(tc--) {
  101. 		solve();
  102. 		// cout<<'\n';
  103. 	}
  104. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2WY2bS
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!