【Codeforces Round #301 (Div. 2) E】Infinite Inversions

给你一个无限长的序列1,2,3,4... 然后给你n个操作. 每个操作ai,bi; 表示调换位置为ai和位置为bi的数的位置。 (ai,bi<=10^9) n个操作结束之后,问你序列中逆序对的个数.

【题解】

肯定和数据结构相关的。那么大,首先离散化一下。然后用离散化后的数字来模拟这个swap的过程。这样,就能够获取出有操作过的数之间的大小关系了。然后用树状数组来处理这些"有操作过的数字"的逆序对。但是还不够。因为可能还有一些数字虽然没有经过处理。但仍然对逆序对有贡献。也即位置为i的被操作过的数字,它原来的位置pos. 那么这里对逆序对有贡献的数字,即i..pos这一段中没有操作过的数字。(这里假设ipos也成立。所以再处理出两个处理过的数字之间没有处理过的数字的前缀和就好了。这样的话就能够快速的获取任意两个位置之间没有操作过的数字的和了。 )>

写题的时候,一直在想着要怎么在线处理。
但实际上这一题并不需要在线处理,只要操作之后知道答案就可以了。
不用什么非常高级的数据结构。

【代码】

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

const int N = 1e5;

int n,num;
pair <int,int> a[N+10];
int X[N*2+10],val[N*2+10],pre[N*2+10];

struct BI {
	int a[2*N + 10];

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

	void add(int x,int y) {
		while (x <= 2*N) {
			a[x] += y;
			x += lowbit(x);
		}
	}

	int sum(int x) {
		int now = 0;
		while (x > 0) {
			now += a[x];
			x -= lowbit(x);
		}
		return now;
	}

	int get_sum(int l, int r) {
		return sum(r) - sum(l - 1);
	}

}b;

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "rt", stdin);
	#endif

	scanf("%d",&n);
	for (int i = 1;i <= n;i++){
		scanf("%d%d",&a[i].first,&a[i].second);
		X[++num] = a[i].first;
		X[++num] = a[i].second;
	}

	sort(X+1,X+1+num);
	num = unique(X+1,X+1+num) - X - 1;
//	printf("%d
",num);

	for (int i = 1;i <= num;i++) val[i] = X[i];
	for (int i = 1;i <= num;i++) pre[i] = pre[i-1] + X[i] - X[i-1] - 1;
    
	for (int i = 1;i <= n;i++){
	 	int x = lower_bound(X+1,X+1+num,a[i].first) - X;
	 	int y = lower_bound(X+1,X+1+num,a[i].second) - X;
	 	swap(val[x],val[y]);
	}

	ll ans = 0;
	for (int i = 1;i <= num;i++){
		int pos = lower_bound(X+1,X+1+num,val[i])-X;
		/*
		printf("now=%d pos=%d temp2 = %d
",i,pos,abs(pre[pos]-pre[i]));
		puts("");
		*/

		ans += b.get_sum(pos,num);
		ans += abs(pre[pos]-pre[i]);
		b.add(pos,1);
	}

	printf("%lld
",ans);
	return 0;
}

【Codeforces Round #301 (Div. 2) E】Infinite Inversions

相关推荐