2019河北省大学生程序设计竞赛（重现赛）E.Paper Plane Fly Away

河北省大学生程序设计竞赛（重现赛）E.Paper Plane Fly Away"/>

2019河北省大学生程序设计竞赛（重现赛）E.Paper Plane Fly Away

题目链接：

题意：现在有 n n n个男孩从 1 1 1到 n n n按照左右顺序坐成一排，同样有 n n n个女孩坐在男孩的前面，第 i i i个男孩前面坐的是编号 a [ i ] a[i] a[i]的女孩。每个男孩都有一个喜欢的女孩，他要做一个情书飞机飞给喜欢的女孩，但是如果飞机的轨迹在空中相交飞机就会相互碰撞，现在你需要得到每个男孩的飞机要和多少个其他男孩的飞机相撞。

解题心得：
将女孩从左到右直接重新编码成 n + 1 n+1 n+1到 2 ∗ n 2*n 2∗n，然后就是一个求逆序对的问题。如果第 i i i个男孩喜欢的女孩编号是 b [ i ] b[i] b[i]，那么他后面的男孩喜欢的女孩比 b [ i ] b[i] b[i]小的和那么他前面的男孩喜欢的女孩比 b [ i ] b[i] b[i]大的都要撞击。在解决第 i i i个男孩时，直接看他喜欢的第 b [ i ] b[i] b[i]个女孩前面还有多少个女孩还没有配对，没配对的在收到飞机的时候肯定会和第 i i i个男孩碰撞，这里需要一个树状数组维护，并且撞击是相互的， b [ i ] b[i] b[i]前面还没配对的女孩收到的飞机碰撞数 + 1 +1 +1，这里还需要一个树状数组维护。

听起来很复杂，其实推推样例就明白了。

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5+100;
typedef long long ll;
map <int, int> maps;//给女生从左到右重新编号
int pre_sum[maxn], sum[maxn], n;//pre_sum[i]是前面i个女生收到的飞机被撞击数量前缀和，sum[i]是前i个女生有多少个已经配对
int num1[maxn], num2[maxn];//num1是女生从左到右的顺序，num2是第i个男生喜欢的女生的编号void init() {scanf("%d", &n);for(int i=1;i<=n;i++) {scanf("%d%d", &num1[i], &num2[i]);maps[num1[i]] = i;}
}int lowbit(int x) {return x & -x;
}int get_sum(int x, int p) {if(x == 0)return 0;int ans = 0;if(p == 0){while(x){ans += pre_sum[x];x -= lowbit(x);}} else {while(x){ans += sum[x];x -= lowbit(x);}}return ans;
}void add(int va, int x, int p) {if(p == 0){while(x <= n){pre_sum[x] += va;x += lowbit(x);}} else {while(x <= n) {sum[x] += va;x += lowbit(x);}}
}int main()
{
//    freopen("in", "r", stdin);init();for(int i=1;i<=n;i++) {int va = num2[i];int ans = get_sum(maps[va], 0);ans += maps[va] - get_sum(maps[va], 1) - 1;printf("%d\n", ans);add(1, 1, 0);add(-1, maps[va], 0);add(1, maps[va], 1);}return 0;
}