fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 5e5 + 5;
  5. int n;
  6. long long bit[MAXN];
  7.  
  8. //Thêm v vào a_p
  9. void add(int p , int v) {
  10.     for(;p<=n;p+=(p&-p)) {
  11.         bit[p] += v;
  12.     }
  13. }
  14. //Tính tổng khi biết i
  15. long long pre(int p) {
  16.     long long sum = 0;
  17.     for(;p>0;p-=(p&-p)) {
  18.         sum += bit[p];
  19.     }
  20.     return sum;
  21. }
  22. //Tính tổng từ l,r
  23. long long query(int l , int r) {
  24.     return pre(r) - pre(l-1);
  25. }
  26. int main() {
  27.     cin>>n;
  28.     vector<long long> a(n);
  29.     map<long long , int> tan_so;
  30.     for(int i=0;i<n;i++) {
  31.         cin>>a[i];
  32.         tan_so[a[i]]++;
  33.     }
  34.     int pos = 0;
  35.     vector<long long> sau_khi_nen;
  36.     for(auto it : tan_so) {
  37.     	sau_khi_nen.push_back(it.first);
  38. 	}
  39. 	vector<long long> idx1(n);
  40. 	for(int i=0;i<n;i++) {
  41. 		long long vt = lower_bound(sau_khi_nen.begin() , sau_khi_nen.end() , a[i]) - sau_khi_nen.begin() + 1;
  42. 		if(vt>1) {
  43. 			idx1[i] = pre(vt-1);
  44. 		}else {
  45. 			idx1[i] = 0;
  46. 		}
  47. 		add(vt , 1);
  48. 	}
  49. 	vector<long long> idx2(n);
  50. 	for(int i=0;i<n;i++) {
  51. 		long long vt = lower_bound(sau_khi_nen.begin() , sau_khi_nen.end() , a[i]) - sau_khi_nen.begin() + 1;
  52. 		if(vt>1) {
  53. 			add(vt , -1);
  54. 			idx2[i] = pre(vt-1);
  55. 		}else {
  56. 			add(vt , -1);
  57. 			idx2[i] = 0;
  58. 		}
  59. 	}
  60. 	long long kq = 0;
  61. 	for(long long i=0;i<n;i++) {
  62. 		kq += idx1[i] * idx2[i];
  63. 	}
  64. 	cout<<kq;
  65.     return 0;
  66. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C1QVnv
language:
C++ (gcc 8.3)
created:
3 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!