fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. const int MPOW=16;
  7. struct sg_tree
  8. {
  9. static const int n=1<<MPOW;
  10. int arr[n];
  11. sg_tree(){fill(arr,arr+n,0);}
  12.  
  13. void add(int x)
  14. {
  15. int cur=x+(1<<MPOW-1);
  16. arr[cur]++;
  17. while(cur>>=1)
  18. arr[cur]=arr[cur<<1]+arr[(cur<<1)+1];
  19. }
  20. int SUM(int c,int cl,int cr,int l,int r)
  21. {
  22. if(l>r)
  23. return 0;
  24. if(l==cl && r==cr)
  25. return arr[c];
  26. int ct=(cl+cr)>>1;
  27. return SUM(c<<1,cl,ct,l,min(r,ct))+SUM((c<<1)+1,ct+1,cr,max(l,ct+1),r);
  28. }
  29. int get_sum(int l,int r)
  30. {return SUM(1,0,(1<<MPOW-1)-1,l,r);}
  31.  
  32. };
  33.  
  34. main()
  35. {
  36. ios::sync_with_stdio(0);
  37. cin.tie(0);
  38. int n;
  39. sg_tree TR;
  40. cin>>n;
  41. int a,b;
  42. vector<int> ans(n);
  43. for(int i=0;i<n;i++)
  44. {
  45. cin>>a>>b;
  46. TR.add(a);
  47. ans[TR.get_sum(0,a)-1]++;
  48. }
  49.  
  50. for(int i=0;i<n;i++)
  51. cout<<ans[i]<<'\n';
  52. }
  53.  
Success #stdin #stdout 0s 3624KB
stdin
5
1 1
5 1
7 1
3 3
5 5
stdout
1
2
1
1
0