1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cmath> 7 using namespace std; 8 long long read() { 9     long long x = 0, f = 1; char ch = getchar();10     while (!isdigit(ch)) {11         if (ch == ‘-‘) f = -1; ch = getchar();12     }13     while (isdigit(ch)) {14         x = x * 10 + ch - ‘0‘; ch = getchar();15     }16     return x * f;17 }18 19 /*------------------------------template------------------------------*/20 21 #define nxt(x) (x & -x)22 #define M 50005023 typedef pair<int, int> pr;24 int a[M << 1];25 long long ans = 0;26 int c[M], b[M];27 int main () {28     int n = read(), x;29         memset(c, 0, sizeof(c));30         memset(a, 0, sizeof(a));31         for (int i = 1; i <= n; i ++) {32             b[i] = c[i] = read();33         }34         sort(b + 1, b + 1 + n);35         int tot = unique(b + 1, b + 1 + n) - b;36         for (int i = 1; i <= n; i ++) {37             c[i] = lower_bound(b + 1, b + tot, c[i]) - b;38         }39         for (int i = 1; i <= n; ans += i ++) {40             x = c[i];41             for (int j = x; j <= n; j += nxt(j)) {42                 a[j] ++;43             }44             for (int j = x; j > 0; j -= nxt(j)) {45                 ans -= a[j];46             }47             //printf("%d %d %d\n", x, i, ans);48         }49         printf("%lld\n", ans); //打成%d调了半天2333333350     return 0;51 }

 1 #include <bits/stdc++.h> 2 using namespace std; 3 long long read() { 4     long long x = 0, f = 1; char ch = getchar(); 5     while (!isdigit(ch)) { 6         if  (ch == ‘-‘) f = -1; ch = getchar(); 7     } 8     while (isdigit(ch)) { 9         x = x * 10 + ch - ‘0‘; ch = getchar();10     }11     return x * f;12 }13 14 /*------------------------------template------------------------------*/15  16 #define M 20200  17 #define nxt(x) (x & -x)18 using namespace std;19 20 int n, m, ans, tot, block;21 int a[M];  22 pair<int, int> b[M];23 int pre[M], cnt[200][M];24 25 void up(int c[], int x) {  26     for(; x <= n; x += nxt(x)) ++c[x];  27 }28 29 void down(int c[], int x) {  30     for(; x <= n; x += nxt(x)) --c[x];  31 }32 33 int calc(int c[], int x) {  34     int re = 0;  35     for(; x; x -= nxt(x)) re+=c[x]; 36     return re;37 }38 39 int main() {  40     int x, y;  41     n = read();  42     for(int i = 1; i <= n; i ++) b[i] = make_pair(read(), i);  43     sort(b + 1, b + n + 1);44     for(int i = 1; i <= n; i ++) {  45         if (b[i].first != b[i - 1].first) ++tot;46         a[b[i].second] = tot;47     }48     for(int i = n; i; i --) ans += calc(pre, a[i] - 1), up(pre, a[i]);  49     printf("%d\n", ans);50     //Get the first ans  51     block = static_cast<int>(sqrt(n) + 1e-7);52     for(int i = 1; i <= n; i ++) up(cnt[(i-1) / block], a[i]);53     //Blocking init54     m = read();55     for(int i = 1; i <= m; i ++) {  56         x = read(); y = read();57         if (x > y) swap(x, y);58         //查询(x, y)区间内有多少个数比a[x]和a[y]小  59         int b1 = (x - 1) / block + 1;  60         int b2 = (y - 1) / block - 1;  61         if (b1 <= b2) {  62             for(int j = b1; j <= b2; j ++) {  63                 ans -= calc(cnt[j], a[x] - 1);  64                 ans += calc(cnt[j], n) - calc(cnt[j], a[x]);  65                 ans += calc(cnt[j], a[y] - 1);  66                 ans -= calc(cnt[j], n) - calc(cnt[j], a[y]);  67             }  68             for(int j = x + 1; j <= b1 * block; j ++) {  69                 if (a[j] < a[x]) --ans;  70                 if (a[j] > a[x]) ++ans;  71                 if (a[j] < a[y]) ++ans;  72                 if (a[j] > a[y]) --ans;  73             }  74             for(int j = (b2 + 1) * block + 1; j < y; j ++) {  75                 if (a[j]<a[x]) --ans;  76                 if (a[j]>a[x]) ++ans;  77                 if (a[j]<a[y]) ++ans;  78                 if (a[j]>a[y]) --ans;  79             }  80         }  81         else {82             //暴力83             for(int j = x + 1; j <= y - 1; j ++) {  84                 if (a[j] < a[x]) --ans;  85                 if (a[j] > a[x]) ++ans;  86                 if (a[j] < a[y]) ++ans;  87                 if (a[j] > a[y]) --ans;  88             }  89         }  90         if (a[x] < a[y]) ++ans;  91         else if (a[x] > a[y]) --ans;  92         printf("%d\n", ans);  93         down(cnt[(x-1) / block], a[x]);  94         down(cnt[(y-1) / block], a[y]);  95         swap(a[x], a[y]);96         up(cnt[(x-1) / block], a[x]);  97         up(cnt[(y-1) / block], a[y]);  98     }  99 }