fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ld long double
  4. #define nl "\n"
  5. #define ull unsigned long long
  6. #define rv return void
  7. #define str string
  8. #define all(x) x.begin(), x.end()
  9. #define allr(x) x.rbegin(), x.rend()
  10. #define vec vector
  11. #define fixed(n) fixed << setprecision(n)
  12. #define Moageza ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
  13. using namespace std;
  14. const ll mod = 1e9+7;
  15. const int N=2e5+5;
  16. const int Qu=2e5+5;
  17. const int SQ=488;
  18. struct Query{
  19.     int l,r,q_idx,blk_idx;
  20.     Query(){}
  21.     Query(int _l,int _r,int _q_idx)
  22.     {
  23.         l=_l,r=_r,q_idx=_q_idx,blk_idx=_l/SQ;
  24.     }
  25.     bool operator<(const Query&Q)const{
  26.         if(blk_idx!=Q.blk_idx)
  27.         {
  28.             return blk_idx<Q.blk_idx;
  29.         }
  30.         return r<Q.r;
  31.     }
  32. };
  33. ll n,q,arr[N],frq[1000006],res=0,ans[Qu];Query qu[Qu];
  34. void add(int idx)
  35. {
  36.    if(!frq[arr[idx]])res++;
  37.    frq[arr[idx]]++;
  38. }
  39. void remove(int idx)
  40. {
  41.     frq[arr[idx]]--;
  42.     if(!frq[arr[idx]])res--;
  43. }
  44. void MO_process()
  45. {
  46.     sort(qu,qu+q);
  47.     int l=1,r=0;
  48.     for(int i=0;i<q;i++)
  49.     {
  50.         while(l<qu[i].l) remove(l++);
  51.         while(l>qu[i].l) add(--l);
  52.         while(r<qu[i].r) add(++r);
  53.         while(r>qu[i].r) remove(r--);
  54.         ans[qu[i].q_idx]=res;
  55.     }
  56. }
  57. void solve() {
  58.     cin>>n;
  59.     for(int i=0;i<n;i++)
  60.     {
  61.         cin>>arr[i];
  62.     }
  63.     cin>>q;
  64.     for(int i=0;i<q;i++)
  65.     {
  66.         int l,r;cin>>l>>r;
  67.         qu[i]=Query(--l,--r,i);
  68.     }
  69.     MO_process();
  70.     for(int i=0;i<q;i++)
  71.     {
  72.         cout<<ans[i]<<'\n';
  73.     }
  74. }
  75. signed main()
  76. {
  77.     Moageza
  78.     #ifndef ONLINE_JUDGE
  79.         freopen("input.txt", "r", stdin);
  80.         freopen("output.txt", "w", stdout);
  81.     #endif
  82.     int t = 1;
  83.     // cin >> t;
  84.     while (t--) {
  85.         solve();
  86.         cout <<nl;
  87.     }
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/ijiyS2
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
9 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!