Atcoder 杂题 round 1

 1 #include <ctime>
 2 #include <cmath>
 3 #include <cctype>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <vector>
10 #include <queue>
11 #define inf 300010
12 #define INF 0x7fffffff
13 #define ll long long
14  
15 template <class I>
16 inline void read(I &num){
17     num = 0; char c = getchar(), up = c;
18     while(!isdigit(c)) up = c, c = getchar();
19     while(isdigit(c)) num = (num << 1) + (num << 3) + (c ^ ‘0‘), c = getchar();
20     up == ‘-‘ ? num = -num : 0; return;
21 }
22 template <class I>
23 inline void read(I &a, I &b) {read(a); read(b);}
24 template <class I>
25 inline void read(I &a, I &b, I &c) {read(a); read(b); read(c);}
26  
27 int n;
28 int a[inf];
29  
30 struct bitTree {
31     private:
32     int c[inf];
33     inline int lowbit(const int &x) {return x & (-x);}
34  
35     public:
36     inline void insert(int x, int k) {
37         ++x;
38         while(x <= n) {
39             c[x] += k;
40             x += lowbit(x);
41         }
42     }
43  
44     inline int query(int x) {
45         ++x; int res = 0;
46         while(x) {
47             res += c[x];
48             x -= lowbit(x);
49         }
50         return res;
51     }
52 };
53  
54 bitTree bt;
55 ll nx[inf], ans[inf];
56  
57 signed main(){
58     read(n);
59     for(int i = 1; i <= n; i++) read(a[i]);
60     for(int i = n; i; i--) {
61         nx[i] = bt.query(a[i]);
62         bt.insert(a[i], 1);
63     }
64     for(int i = 1; i <= n; i++) ans[0] += nx[i];
65     for(int i = 1; i < n; i++) {
66         ans[i] = ans[i - 1] - a[i] + (n - 1 - a[i]);
67     }
68     for(int i = 0; i < n; i++) printf("%lld\n", ans[i]);
69     return 0;
70 }