fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define str string
  3. #define ll long long
  4. #define db double
  5. using namespace std;
  6.  
  7. const int mod=1e9+7;
  8.  
  9. int cnt[32][1200004], a[300001], lazy[32][1200004];
  10.  
  11. void push(int id, int l, int r, int val){
  12. 	if(lazy[val][id]){
  13. 		if(lazy[val][id]>0){
  14. 			cnt[val][id*2]=(r-l+2)/2;
  15. 			cnt[val][id*2+1]=(r-l+1)/2;
  16. 		}else{
  17. 			cnt[val][id*2]=0;
  18. 			cnt[val][id*2+1]=0;
  19. 		}
  20. 		lazy[val][id*2]=lazy[val][id];
  21. 		lazy[val][id*2+1]=lazy[val][id];
  22. 		lazy[val][id]=0;
  23. 	}
  24. }
  25.  
  26. void build(int id, int l, int r, int val){
  27. 	if(l==r){
  28. 		if(a[l]==val)cnt[val][id]=1;
  29. 		else cnt[val][id]=0;
  30. 		return;
  31. 	}
  32. 	int m=(l+r-1)/2;
  33. 	build(id*2, l, m, val);
  34. 	build(id*2+1, m+1, r, val);
  35. 	cnt[val][id]=cnt[val][id*2]+cnt[val][id*2+1];
  36. }
  37.  
  38. int get(int id, int l, int r, int u, int v, int val){
  39. 	if(u<=l && r<=v)return cnt[val][id];
  40. 	int m=(l+r-1)/2, left=0, right=0;
  41. 	push(id, l, r, val);
  42. 	if(!(u>m || v<l))left=get(id*2, l, m, u, v, val);
  43. 	if(!(u>r || v<m+1))right=get(id*2+1, m+1, r, u, v, val);
  44. 	return left+right;
  45. }
  46.  
  47. void update(int id, int l, int r, int u, int v, int val, int type){
  48. 	if(u<=l && r<=v){
  49. 		if(type){
  50. 			cnt[val][id]=r-l+1;
  51. 			lazy[val][id]=1;
  52. 		}else{
  53. 			cnt[val][id]=0;
  54. 			lazy[val][id]=-1;
  55. 		}
  56. 		return;
  57. 	}
  58. 	int m=(l+r-1)/2;
  59. 	push(id, l, r, val);
  60. 	if(!(u>m || v<l))update(id*2, l, m, u, v, val, type);
  61. 	if(!(u>r || v<m+1))update(id*2+1, m+1, r, u, v, val, type);
  62. 	cnt[val][id]=cnt[val][id*2]+cnt[val][id*2+1];
  63. }
  64.  
  65. int main(){
  66. 	ios_base::sync_with_stdio(false);
  67. 	cin.tie(0); cout.tie(0);
  68. 	freopen("mexquery.inp", "r", stdin);
  69. 	freopen("mexquery.out", "w", stdout);
  70. 	int n; cin>>n;
  71. 	for(int i=0; i<n; ++i)cin>>a[i];
  72. 	for(int i=0; i<=30; ++i)build(1, 0, n-1, i);
  73. 	int q; cin>>q;
  74. 	while(q--){
  75. 		int tmp;
  76. 		cin>>tmp;
  77. 		if(tmp==2){
  78. 			int l, r; cin>>l>>r;
  79. 			l--; r--;
  80. 			for(int i=0; i<=31; ++i){
  81. 				if(!get(1, 0, n-1, l, r, i)){
  82. 					cout<<i<<'\n';
  83. 					break;
  84. 				}
  85. 			}
  86. 		}else{
  87. 			int u, v, type; cin>>u>>v>>type;
  88. 			u--; v--;
  89. 			vector<int> curr_cnt(31, 0);
  90. 			for(int i=0; i<=30; ++i){
  91. 				curr_cnt[i]=get(1, 0, n-1, u, v, i);
  92. 				update(1, 0, n-1, u, v, i, 0);
  93. 			}
  94. 			v=u;
  95. 			if(type==1){
  96. 				for(int i=0; i<=30; ++i){
  97. 					v+=curr_cnt[i];
  98. 					if(curr_cnt[i])update(1, 0, n-1, u, v-1, i, 1);
  99. 					u+=curr_cnt[i];
  100. 				}
  101. 			}else{
  102. 				for(int i=30; i>=0; --i){
  103. 					v+=curr_cnt[i];
  104. 					if(curr_cnt[i])update(1, 0, n-1, u, v-1, i, 1);
  105. 					u+=curr_cnt[i];
  106. 				}
  107. 			}
  108. 		}
  109. 	}
  110. 	return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 65288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yBrFPZ
language:
C++ (gcc 8.3)
created:
2 days 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!