H2. Maximum Crossings (Hard Version)

题目大意：

有两条平行的线段，点line1[i]和line2[ai]相连。问最多有几个交点。

思路和代码：

今天吃午饭的时候队里的神犇杰锅来跟我炫耀，吹水间跟我说了这个题目。我来补一下。

首先把题目转化成，[1,i-1]中有多少个点大于等于ai。又考虑到ai的范围是2e5。

所以只要做一个桶tr，每次判断一下ai在[1，i-1]中出现了几次，即直接引用tr[ai]即可。

再把[1，ai]这个范围里的tr全部加1，即可维护出[1,i-1]中有多少个数大于等于ai。

而以上维护操作就是一个区间修改单点查询的问题，可以直接用线段树做，但是利用差分树状数组可以更加快乐。

利用差分树状数组就是把区间修改单点查询转化成单点修改前缀和的过程。

/*
BIT
区间查询 单点修改 

差分BIT
单点查询 区间修改 
*/
int n , m , k ; 

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

ll query(int x , vct &tr){
	ll res = 0 ;
	while(x) res += tr[x] , x -= lowbit(x) ;
	return res ;
}

void add(int x , int det , vct &tr){
	
	for(int i = x ; i <= n ; i += lowbit(i))
		tr[i] += det ;
}

void solve(){
	cin >> n ;
	vct a(n + 1 , 0) ;
	vct tr(n + 2 , 0) ;
	rep(i , 1 , n) cin >> a[i] ;
	
	ll ans = 0 ;
	rep(i , 1 , n){
		int num = query(a[i] , tr) ;
		ans += num ;
		add(1 , 1 , tr) ;
		add(a[i] + 1 , -1 , tr) ;
	}
	cout << ans << "\n" ;
	
}//code_by_tyrii 

小结：

这题主要难在如何将“[1,i-1]中大于等于ai的数量”转化成一个树状数组的问题。

好题！