fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define maxn 100010
  5. #define ena long long
  6.  
  7. ena n;
  8. ena a[maxn], cnt[maxn], st[4*maxn], ans[maxn];
  9.  
  10. vector <ena> vitri[maxn];
  11.  
  12. void update(ena node, ena l, ena r, ena id, ena val)
  13. {
  14. if(id < l || id > r) return;
  15. if(l == r)
  16. {
  17. st[node] += val;
  18. return;
  19. }
  20. ena mid = (l + r)/2;
  21. update(2*node, l, mid, id, val);
  22. update(2*node+1, mid+1, r, id, val);
  23.  
  24. st[node] = st[2*node] + st[2*node+1];
  25. }
  26.  
  27. ena get(ena node, ena l, ena r, ena u, ena v)
  28. {
  29. if(v < l || r < u) return 0;
  30. if(u <= l && r <= v) return st[node];
  31.  
  32. ena mid = (l + r)/2;
  33. ena L = get(2*node, l, mid, u, v);
  34. ena R = get(2*node+1, mid+1, r, u, v);
  35.  
  36. return (L + R);
  37. }
  38.  
  39. int main()
  40. {
  41. freopen("daonguoc.inp","r",stdin);
  42. freopen("daonguoc.out","w",stdout);
  43. cin >> n;
  44. for(ena i=1; i<=n; i++)
  45. {
  46. cin >> a[i];
  47. cnt[i] = get(1, 0, n, a[i] + 1, n);
  48. update(1, 0, n, a[i], 1);
  49. vitri[a[i]].push_back(i);
  50.  
  51. ans[n] += cnt[i];
  52. }
  53.  
  54. for(ena i=n-1; i>=0; i--)
  55. {
  56. ans[i] = ans[i+1];
  57. for(ena id:vitri[i])
  58. {
  59. ans[i] -= cnt[id];
  60. }
  61. }
  62.  
  63. for(ena i=0; i<=n-1; i++)
  64. cout << ans[i] << "\n";
  65. return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 7164KB
stdin
Standard input is empty
stdout
Standard output is empty