2019河北省大学生程序设计竞赛 E

题目：https://ac.nowcoder.com/acm/contest/903/E

链接：https://ac.nowcoder.com/acm/contest/903/E
来源：牛客网
 

There are n boys, indexed from 1 to n, and n girls indexed from n+1 to 2n.
One day, they have a party together. The girls are seated in the first row, and the boys sit in the second row. They take their seat in such a way, that a boy sit just behind a girl, and boy indexed 1 sit on the leftmost chair, 2 sit on the second, etc.
Each boy has a girl he likes,and he may make contact to his sweetheart, by writing down what he wants to tell her on a piece of paper, and makes it a paper plane, which he will throw directly at her. You may assume that the plane will go in a straight line.
But, the trouble occurs, when two paper plane collide in the air and drop halfway. Obviously, this will be extremely awkward. So each boy wants to know, if he throws his paper plane, how many paper planes have the potential to collide with it halfway.
It's guaranteed that each girl is the sweetheart of exactly one boy.

输入描述:

The first line contains a single integer n.
Then n lines follow, the i-th of which contains two integers, the index of the girl seated in front of the i-th boy and the girl he likes.
1≤n≤1051≤n≤105

输出描述:

Output n lines, the i-th of which contains one integer, the number of planes that may collide with i-th boy's plane.

示例1

输入

复制

5
7 9
6 6
8 10
9 7
10 8

输出

复制

3
2
2
3
2

题意：第一排坐的女生，顺序由题目给出，第二排坐的是男生，顺序是从左到右编号是1——n，女生的编号是n+1——2*n，

每个男生有一个喜欢的女生，并且没有两个男生喜欢同一个女生。每个男生和他喜欢的女生连线，题目的意思就相当于求与每条线相交的数目。

思路：

         每个女生的编号我们降为1——n处理，从左到右依次处理每一个男生，男生喜欢的女生的编号是mp[to[i]],to[i]是第i个男生喜欢的女生，sum2[i]表示前i个女生中已经匹配了的女生数量，sum1[i]表示前i个女生中已经和后i个男生匹配的数量，分别用两个树状数组维护这两个值，

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 * 1000 + 10;
int f[maxn], to[maxn],n;
int sum1[maxn], sum2[maxn];
map<int, int>mp;

int lowerbit(int x) { return x & -x; }

int query(int x,int k) {
	int ans = 0;
	if (k == 1) {
		while (x)ans += sum1[x], x -= lowerbit(x);
	}
	else {
		while (x)ans += sum2[x], x -= lowerbit(x);
	}
	return ans;
}


void add(int v, int x, int k) {
	if (k == 1) {
		while (x <= n)sum1[x] += v, x += lowerbit(x);
	}
	else {
		while (x <= n)sum2[x] += v, x += lowerbit(x);
	}
}

int main(){

	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d",&f[i],&to[i]);
		mp[f[i]] = i;
	}
	
	for (int i = 1; i <= n; i++) {
		int ans = 0;
		int index = mp[to[i]];
		ans += query(index,1);
		ans += index - query(index,2)-1;
		printf("%d\n",ans);
		add(1,1,1);
		add(-1,index,1);
		add(1,index,2);
	}
	return 0;
}