首页 > 代码库 > CF 540E, 树状数组

CF 540E, 树状数组

2024-08-13 11:33:31   214人阅读

题目大意：在1~10^9的范围内随便交换某些位置上的数，求逆序对数量，交换位置<=10^5

解：因为是交换位置很少，离散化来做，逆序对可以看成两部分，一部分是出现位置的逆序对，另一部分的出现了的数对于没有交换位置上的数（没有在离散化中出现的数）的逆序对。分别统计一下，第一part用树状数组，第二part之间算一下区间实际的数字和有多少个交换了位置的数字即可。

 

技术分享
 1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <utility> 5 #include <map> 6 #include <string> 7 #include <cmath> 8 #include <vector> 9 #include <cstring>10 11 using namespace std;12 13 #define SQR(x) ((x)*(x))14 #define LL long long15 #define LOWBIT(x) ((x)&(-(x)))16 #define PB push_back17 #define MP make_pair18 19 #define MAXN 21111120 21 struct TreeArray{22     int tree[MAXN], n;23     void clear(int nn = MAXN - 10) {24         n = nn;25         memset(tree, 0, sizeof(tree[0]) * (n + 10));26     }27     void add(int x, int num = 1) {28         while (x <= n) {29             tree[x] += num;30             x += LOWBIT(x);31         }32     }33     int get(int x) {34         int res = 0;35         while (x > 0) {36             res += tree[x];37             x -= LOWBIT(x);38         }39         return res;40     }41 } TA;42 43 pair<int, int > query[MAXN];44 vector <int > lsh;45 vector <int > a;46 int n;47 LL ans;48 49 void init() {50     cin >> n;51     int x, y;52     lsh.clear();53     for (int i = 0; i < n; ++i) {54         cin >> x >> y;55         query[i] = MP(x, y);56         lsh.PB(x); lsh.PB(y);57     }58     sort(lsh.begin(), lsh.end()); 59     lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());60 }61 62 #define INDEX(x) ((lower_bound(lsh.begin(), lsh.end(), (x))-lsh.begin())+1)63 64 void solve() {65     ans = 0;66     a = lsh;67     TA.clear(lsh.size()+10);68     for (int i = 0; i < n; ++i) {69 //        cout << query[i].first <<‘ ‘<< query[i].second << endl;70         swap(a[INDEX(query[i].first)-1], a[INDEX(query[i].second)-1]);71     }72 73 //    for (int i = 0; i < lsh.size(); ++i) cout << lsh[i] <<‘ ‘; cout << endl;74 //    for (int i = 0; i < a.size(); ++i) cout << a[i] <<‘ ‘; cout << endl;75 76     for (int i = (int)a.size() - 1; i >= 0; --i) {77         ans += TA.get(INDEX(a[i]) - 1);78         TA.add(INDEX(a[i]));79         int key = 0, t;80         t = INDEX(a[i]) - 1;81         if (i < t) {82             key = (lsh[t] - lsh[i] - 1) - (t - i - 1);83         } 84         else {85             key = (lsh[i] - lsh[t] - 1) - (i - t - 1);86         }87         ans += key;88 //        cout << ans << endl;89     }90 }91 92 int main() {93 //    freopen("test.txt", "r", stdin);94     ios::sync_with_stdio(false);95     init();96     solve();97     cout << ans << endl;98     return 0;99 }
CF 540E

 

CF 540E, 树状数组


联系
我们