fork(1) download
copy 
  1. /*input
  2. 5
  3. 1 2 3 4 5
  4. 2
  5. 1 4 1 2
  6. 1 4 2 3
  7. */
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. #define sp ' '
  11. #define endl '\n'
  12.  
  13. const int BLOCK_SIZE = 800;
  14. const int N = 2e5 + 5;
  15. const int LIM = 100;
  16. int n, nblocks;
  17. int a[N];
  18. int lazy[N / BLOCK_SIZE + 1][LIM + 1];
  19.  
  20. void doLazy(int id) { // L R là đầu trái và đầu phải của phần dư bên trái
  21.     int L = id * BLOCK_SIZE;
  22.     int R = min(n - 1, (id + 1) * BLOCK_SIZE - 1);
  23.     for (int i = L; i <= R; i++) {
  24.         a[i] = lazy[id][a[i]]; // thay đổi giá trị các phần tử bằng mảng lazy
  25.     }
  26.     for (int i = 1; i <= 100; i++) {
  27.         lazy[id][i] = i; // đã cập nhật xong, reset lại mảng lazy về ban đầu
  28.     }
  29. }
  30.  
  31. void manualUpdate(int L, int R, int oval, int nval) { // L R là đầu trái và đầu phải của phần dư bên trái
  32.     int id = R / BLOCK_SIZE;
  33.     doLazy(id);
  34.     for (int i = L; i <= R; i++) {
  35.         if (a[i] == oval) {
  36.             a[i] = nval;
  37.         }
  38.     }
  39. }
  40.  
  41. void blockUpdate(int id, int oval, int nval) {
  42.     for (int i = 1; i <= LIM; i++) {
  43.         if (lazy[id][i] == oval) {
  44.             lazy[id][i] = nval;
  45.         }
  46.     }
  47. }
  48.  
  49. void update(int l, int r, int oval, int nval) {
  50.     int blockL = l / BLOCK_SIZE, blockR = r / BLOCK_SIZE;
  51.     if (blockL == blockR) {
  52.         manualUpdate(l, r, oval, nval);
  53.         return;
  54.     }
  55.     for (int i = blockL + 1; i < blockR; ++i) {
  56.         blockUpdate(i, oval, nval);
  57.     }
  58.     manualUpdate(l, (blockL + 1) * BLOCK_SIZE - 1, oval, nval);
  59.     manualUpdate(blockR * BLOCK_SIZE, r, oval, nval);
  60. }
  61.  
  62. void init() {
  63.     nblocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
  64.     for (int i = 0; i < nblocks; i++) {
  65.         for (int j = 1; j <= 100; j++) {
  66.             lazy[i][j] = j;
  67.         }
  68.     }
  69. }
  70.  
  71. signed main() {
  72.     ios_base::sync_with_stdio(false); cin.tie(nullptr);
  73.     cin >> n;
  74.     for (int i = 0; i < n; i++) {
  75.         cin >> a[i];
  76.     }
  77.     init();
  78.     int q; cin >> q;
  79.     for (int Q = 0; Q < q; Q++) {
  80.         int l, r, oval, nval;
  81.         cin >> l >> r >> oval >> nval;
  82.         l--; r--;
  83.         update(l, r, oval, nval);
  84.     }
  85.     for (int i = 0; i < nblocks; i++) {
  86.         doLazy(i);
  87.     }
  88.     for (int i = 0; i < n; i++) {
  89.         cout << a[i] << sp;
  90.     }
  91.     cout << endl;
  92. }
Success #stdin #stdout 0s 4944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/TA4XqI
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
3 years 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!