SHARE
TWEET

AIB

a guest Mar 25th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. ifstream fin("aib.in");
  7. ofstream fout("aib.out");
  8.  
  9. #define NMAX 100005
  10.  
  11. int zero(int x)
  12. {
  13.     return (x^(x-1)&x);
  14. }
  15.  
  16. int x,aib[NMAX],n;
  17.  
  18. void update(int x)
  19. {
  20.     for(int i=x;i<=n;i+=zero(i))
  21.         aib[i]++;
  22. }
  23.  
  24. int query(int x)
  25. {
  26.     int s=0;
  27.     for(int i=x;i>0;i-=zero(i))
  28.         s+=aib[i];
  29.     return s;
  30. }
  31.  
  32.  
  33.  
  34. int main()
  35. {
  36.     cin>>n;
  37.     for(int i=1;i<=n;i++)
  38.     {
  39.         cin>>x;
  40.         cout<<query(x-1)<<" ";
  41.         update(x);
  42.     }
  43.  
  44.  
  45.  
  46.     return 0;
  47. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top